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

中文版

在過(guò)去，F(xiàn)armer John曾經(jīng)構(gòu)思了許多新式奶牛運(yùn)動(dòng)項(xiàng)目的點(diǎn)子，其中就包括奶牛障礙賽，是奶牛們?cè)谫惖郎吓茉秸系K欄架的競(jìng)速項(xiàng)目。他之前對(duì)推廣這項(xiàng)運(yùn)動(dòng)做出的努力結(jié)果喜憂參半，所以他希望在他的農(nóng)場(chǎng)上建造一個(gè)更大的奶牛障礙賽的場(chǎng)地，試著讓這項(xiàng)運(yùn)動(dòng)更加普及。

Farmer John為新場(chǎng)地精心設(shè)計(jì)了NN個(gè)障礙欄架，編號(hào)為1…N1…N（2≤N≤1052≤N≤105），每一個(gè)欄架都可以用這一場(chǎng)地的二維地圖中的一條線段來(lái)表示。這些線段本應(yīng)兩兩不相交，包括端點(diǎn)位置。

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

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

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

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

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

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

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

輸出樣例：
2

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

供題：Brian Dean