Problem description ：

There is a straight line , From origin to infinity .

There are on this line N Line segments . Line segments may intersect .

ask ,N How long are the lines covered in total ?( Areas covered repeatedly are calculated only once )

================================================

Thinking of problem solving ：

You can split each segment into “ Company 1”

Traverse all segments , Use an array to record what each line segment passes through “ Company 1”

Finally, count the passed in the array “ Company 1” The number of , This is the total length covered by all segments .

There's a problem here ? How to determine the size of an array ?

The size of the array should be the largest endpoint coordinate of all segments .

===============================================

By the way, I have a question .

Several line segments are given . How many, please “ Connected domain ”. It's the line segments that will be able to merge Merge into one line segment .

Finally, several can be merged ?

Use the ideas above . It's simple .

Just make a start and end record when traversing the unit array .

The program is implemented as follows .

===============================================
// Requirements for this question // Find out the length of the whole line covered by all the line segments . // The overlap is calculated only once .
//================================ // The idea of this algorithm is , Pixel each line segment , // Add to an array of units c[N] in
// ergodic c Array to determine which units are covered , // stay count Count it and you'll know how many miles it covers . // How clever .
//============================== #include <iostream> using namespace std; const
int N = 10000; // Segment structure struct Segment { int start; int end; }; // int
coverage(Segment *segments, int n) { bool c[N]={false};// each “ Company 1” Is it covered int
start=0; int end = 0; // ergodic n Line segments for(int i = 0; i < n; i++) { for(int j =
segments[i].start; j < segments[i].end; j++) { c[j] = true; } // Look for the rightmost end
if(segments[i].end > end) { end = segments[i].end; } // Look for the far left
if(segments[i].start < start) { start = segments[i].start; } }
// From the far left to the right . Traversing unit array C int count = 0; for(int i= start; i < end; i++) { if(c[i])
{ int s=i; while(c[i]) { count++; i++; } int e=i; cout <<
"["<<s<<","<<e<<"]"<<endl; } } return count; }; int main() { Segment s1;
s1.start = 1; s1.end = 3; Segment s2; s2.start = 2; s2.end = 6; Segment s3;
s3.start = 11; s3.end = 12; Segment s4; s4.start = 10; s4.end = 13; Segment
ss[] = {s1,s2,s3,s4}; cout << " After merger "<<endl; cout <<" Total length covered ：" <<coverage(ss,
sizeof(ss)/sizeof(ss[0]))<<endl; }
The output results are as follows ：

After merger
[1,6]
[10,13]

Total length covered
8

Please press any key to continue . .

Technology
Daily Recommendation
views 2