How to find maximum number of intersectionS through set of line segments [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

Suppose I am given number of lines segments in Cartesian coordinate system.Each line is given as [x0,y0] and [x1,y1].Algorithm should find a perpendicular that cross maximum number of lines. In this example it crosses four lines:

What开发者_运维问答 algorithm can do it with minimum complexity?(i would prefer c++ but some kind of pseudo code is OK too)

P.S The point to think about is when several lines start/end in the same x coordinate

Thank you.

---

1. Convert each line to a interval of [x_start,x_end] for each segment.
2. Create a datastructure that contains a flag for whether it is a start or end point, as well as the point value.
3. Sort all the points and then iterate through them incrementing a counter when you hit a start point and decrementing a counter when you hit an end point. Keep track of the maximum value.
4. Repeat with the Y values if desired.

O(n lg n) time complexity

---

If you want perpendicular, then here y aren't needed. The algorithm is following.

1. Sort lines to x0 be lower-equal to x1
2. put all points to seperate array in sorted orden and with point store a flag which tells if the point is start or end of line

3. Run on array and get the segment which belong in maximal number of given intervals

   vector<pair<double, unsigned char> > points; // (point, flag) pairs
   //read [x0, x1]s to points, be sure that x0 <= x1 (swap them otherwise)
   //0 for x0, 1 for x1
   sort(points.begin(), points.end());
   int ans = 0;
   int curstate = 0;
   for(int i = 0; i < points.size(); ++i)
   {
       if(points[i].second == 0)
           ++curstate;
       else
           --curstate;
       ans = max(ans, curstate);
   }
   

---

Iterate through the combinations of the existing lines. Build a list for each iteration containing all the other lines that are not perpendicular to the current line. Sort the lists into descending order by size. The (first) list with the largest size will be the solution. It will contain a list of lines that are crossed. There are an infinite number of lines that would be solutions. Send some of your salary to me as a royalty ;)