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

中文版

在过去，Farmer John曾经构思了许多新式奶牛运动项目的点子，其中就包括奶牛障碍赛，是奶牛们在赛道上跑越障碍栏架的竞速项目。他之前对推广这项运动做出的努力结果喜忧参半，所以他希望在他的农场上建造一个更大的奶牛障碍赛的场地，试着让这项运动更加普及。

Farmer John为新场地精心设计了NN个障碍栏架，编号为1…N1…N（2≤N≤1052≤N≤105），每一个栏架都可以用这一场地的二维地图中的一条线段来表示。这些线段本应两两不相交，包括端点位置。

不幸的是，Farmer John在绘制场地地图的时候不够仔细，现在发现线段之间出现了交点。然而，他同时注意到只要移除一条线段，这张地图就可以恢复到预期没有相交线段的状态（包括端点位置）。

请求出Farmer John为了恢复没有线段相交这一属性所需要从他的计划中删去的一条线段。如果有多条线段移除后均可满足条件，请输出在输入中出现最早的线段的序号。

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

输入的第一行包含NN。余下NN行每行用四个整数x1x1 y1y1 x2x2 y2y2表示一条线段，均为至多109109的非负整数。这条线段的端点为(x1,y1)(x1,y1)和(x2,y2)(x2,y2)。所有线段的端点各不相同。

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

输出在输入中出现最早的移除之后可以使得余下线段各不相交的线段序号。

输入样例：
4
2 1 6 1
4 0 1 5
5 6 5 5
2 7 1 3

输出样例：
2

注意：由于线段端点坐标数值的大小，在这个问题中你可能需要考虑整数类型溢出的情况。

供题：Brian Dean