c - Optimizing a simple pinball solver -

I am trying to solve a programming challenge and only have been successful in doing so partially; I need to optimize the solution - and that is where you come in. First, the parameter:

• You have given some line segments int x1, y1, x2, y2 .
• You are given a starting point for your ball, int px, py = INT_MAX .
• When you take a line through a
  • this line moves to its lower end point
  • When no more lines give each other a hole, output px .

So, what do I think:

• Line Tuples int xtop, ytop, xbot, ybot list,
• Sort the lines from ybot . This allows us to leave the lines that have passed the ball,
• Track index imin such as lines [i] .ybot> = Py For all i & lt; Imin , no difference is found by:
  • Maximize vertical interaction yi = kx + m ,
  • set Px, py = lines [i]. {X, y} bot .

The problem is that this time in complexity &; & Theta; (N ² ) - IOW, it is useless for large inputs.

There is a way to use something, but then the question is that it will not be too much, it is expensive to calculate which lines are known, which is called half-place.

I'm interested in the slab decomposition method that I've linked to is one of the simplest options ; In short, you increase the vertical lines from each end point of a segment, make 2n + 1 vertical slab for each slab, you calculate a binary tree which indicates, From top to bottom, the clauses cross the slab. Then, where the ball is hit, find out which slab it is and then in which section it hits (if any); Both operations are O (log n) -time.

To calculate binary trees in the first place, use sweep line algorithms. Start with the empty binary tree and process the end points in the sequential order of the X-coordinate. For the left end point, enter the segment in the tree. For the right, remove it from the tree, assuming that the segments are not being crossed, there is no need to sort them within the tree. Naively, we have to copy the tree after each stage, but o (n ^ 2) to O (n log n) is an easy strategy to obtain storage using a purely functional red-black tree, For which to disregard the requirement copies

The overall running time and location for this approach is O (n log n).