P6920: 奶牛障碍赛II
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
在过去，Farmer John
曾经构思了许多新式奶牛运动项目的点子，其中就包括奶牛障碍赛，是奶牛们在赛道上跑越障碍栏架的竞速项目。他之前对推广这项运动做出的努力结果喜忧参半，所以他希望在他的农场上建造一个更大的奶牛障碍赛的场地，试着让这项运动更加普及。
Farmer John
为新场地精心设计了N个障碍栏架，编号为1…N
（2≤N≤10
^5
），每一个栏架都可以用这一场地的二维地图中的一条线段来表示。这些线段本应两两不相交，包括端点位置。
不幸的是，Farmer John
在绘制场地地图的时候不够仔细，现在发现线段之间出现了交点。然而，他同时注意到只要移除一条线段，这张地图就可以恢复到预期没有相交线段的状态（包括端点位置）。
请求出Farmer John
为了恢复没有线段相交这一属性所需要从他的计划中删去的一条线段。如果有多条线段移除后均可满足条件，请输出在输入中出现最早的线段的序号。
【
输入格式】
（文件名：cowjump.in
）：
输入的第一行包含N
。余下N
行每行用四个整数x1 y1 x2 y2
表示一条线段，均为至多10
^9
的非负整数。这条线段的端点为(x1,y1)
和(x2,y2)
。所有线段的端点各不相同。
【
输出格式】
（文件名：cowjump.out
）：
输出在输入中出现最早的移除之后可以使得余下线段各不相交的线段序号。
【
输入样例】
：
4
2 1 6 1
4 0 1 5
5 6 5 5
2 7 1 3
【
输出样例】
：
2
注意：由于线段端点坐标数值的大小，在这个问题中你可能需要考虑整数类型溢出的情况。