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

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

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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

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

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 Copy 

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

Sample Output Copy 

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.

Source/Category

USACO Silver 
[Submit] [Status]