USACO 2019 US Open Contest, Silver Problem 2 Cow Steeplechase II

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?NN?hurdles, conveniently numbered?1…N1…N?(2≤N≤105(2≤N≤105), 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.

INPUT FORMAT (file cowjump.in):

The first line of input contains?NN. Each of the?NN?remaining lines describe one line segment with four integers?x1x1?y1y1?x2x2?y2y2, all nonnegative integers at most?109109. The line segment has?(x1,y1)(x1,y1)?and?(x2,y2)(x2,y2)?as?its endpoints. All endpoints are distinct from each-other.

OUTPUT FORMAT (file cowjump.out):

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

SAMPLE INPUT:
4
2 1 6 1
4 0 1 5
5 6 5 5
2 7 1 3

SAMPLE OUTPUT:
2

Note: You may want to be careful of integer overflow in this problem, due to the size of the integers provided?as?coordinates of segment endpoints.

Problem credits: Brian Dean

中文版

在過去，F(xiàn)armer John曾經構思了許多新式奶牛運動項目的點子，其中就包括奶牛障礙賽，是奶牛們在賽道上跑越障礙欄架的競速項目。他之前對推廣這項運動做出的努力結果喜憂參半，所以他希望在他的農場上建造一個更大的奶牛障礙賽的場地，試著讓這項運動更加普及。

Farmer John為新場地精心設計了NN個障礙欄架，編號為1…N1…N（2≤N≤1052≤N≤105），每一個欄架都可以用這一場地的二維地圖中的一條線段來表示。這些線段本應兩兩不相交，包括端點位置。

不幸的是，F(xiàn)armer John在繪制場地地圖的時候不夠仔細，現(xiàn)在發(fā)現(xiàn)線段之間出現(xiàn)了交點。然而，他同時注意到只要移除一條線段，這張地圖就可以恢復到預期沒有相交線段的狀態(tài)（包括端點位置）。

請求出Farmer John為了恢復沒有線段相交這一屬性所需要從他的計劃中刪去的一條線段。如果有多條線段移除后均可滿足條件，請輸出在輸入中出現(xiàn)最早的線段的序號。

輸入格式（文件名：cowjump.in）：

輸入的第一行包含NN。余下NN行每行用四個整數(shù)x1x1?y1y1?x2x2?y2y2表示一條線段，均為至多109109的非負整數(shù)。這條線段的端點為(x1,y1)(x1,y1)和(x2,y2)(x2,y2)。所有線段的端點各不相同。

輸出格式（文件名：cowjump.out）：

輸出在輸入中出現(xiàn)最早的移除之后可以使得余下線段各不相交的線段序號。

輸入樣例：
4
2 1 6 1
4 0 1 5
5 6 5 5
2 7 1 3

輸出樣例：
2

注意：由于線段端點坐標數(shù)值的大小，在這個問題中你可能需要考慮整數(shù)類型溢出的情況。

供題：Brian Dean