P5428 [USACO19OPEN] Cow Steeplechase II S

In the past, Farmer John has come up with many ideas for new cow sports, including cow steeplechase, a racing event where cows run along a track and jump over hurdles. His previous efforts to promote this sport had mixed results, so he wants to build a larger cow steeplechase venue on his farm to try to make the sport more popular. Farmer John carefully designed $N$ hurdles for the new venue, numbered $1 \ldots N$ ($2 \leq N \leq 10^5$). Each hurdle can be represented as a line segment on the 2D map of the venue. These segments were supposed to be pairwise non-intersecting, including at endpoints. Unfortunately, Farmer John was not careful enough when drawing the map and now finds that there are intersections between segments. However, he also notices that as long as he removes one segment, the map can be restored to the intended state where no segments intersect (including at endpoints). Please find one segment that Farmer John needs to delete from his plan to restore the property that no segments intersect. If removing multiple segments can satisfy the condition, output the index of the segment that appears earliest in the input.

The first line contains $N$. The next $N$ lines each contain four integers $x_1, y_1, x_2, y_2$, all non-negative integers of value at most $10^9$, describing a segment. The endpoints of the segment are $(x_1, y_1)$ and $(x_2, y_2)$. All segment endpoints are distinct.

Output the index of the earliest segment in the input such that after removing it, all remaining segments are pairwise non-intersecting.

Note: Because the endpoint coordinates can be very large, you may need to consider integer overflow in this problem. Translated by ChatGPT 5