In the past, Farmer John had contemplated a number of innovative ideas for new
cow sports, among them Cow Steeplechase, where herds of cows would race around a
course and jump over hurdles. His past efforts to build interest in this sport
have met with mixed results, so he is hoping to build an even larger Cow
Steeplechase course on his farm to try and create more publicity for the sport.

Farmer John's new course is carefully planned around \(N\) hurdles, conveniently
numbered \(1 \ldots N\) \((2 \leq N \leq 10^5\)), each one described as a line
segment on the 2D map of the course. These line segments should not intersect
each-other in any way, even their at endpoints.

Unfortunately, Farmer John wasn't paying attention when crafting the course map
and notices that there are intersections between segments. However, he also
notices that if he takes away just one segment, the map is restored to its
intended state of having no intersecting segments (not even at endpoints).

Please determine a line segment Farmer John can remove from his plan to restore
the property that no segments intersect. If multiple segments are possible to
remove in this way, please output the index of the earliest one in the input.

Problem credits: Brian Dean

Problem credits: Brian Dean

The first line of input contains \(N\). Each of the \(N\) remaining lines describe
one line segment with four integers \(x_1\) \(y_1\) \(x_2\) \(y_2\), all nonnegative
integers at most \(10^9\). The line segment has \((x_1, y_1)\) and \((x_2, y_2)\) as
its endpoints. All endpoints are distinct from each-other.

Output the earliest index within the input of a segment such that removing that
segment causes the remaining segments not to intersect.

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > US Open > Silver