93 #P1212. G50 叉积应用 线线关系*【计算几何:叉积】判断线段相交[POJ2653]

G50 叉积应用 线线关系*【计算几何:叉积】判断线段相交[POJ2653]

【题意】

nn 条线段(编号为11nn),按 11nn 的顺序放在二维坐标系上(先放1号线段,再放2号线段 …… )。

要求输出最上面的那些线段的编号(就是没有其他线段压在它上面的那些线段)。

【输入格式】

第一行一个数 nn1n100001 \le n \le 10000 )。

下来 nn 行,每行两个坐标,表示第i条线段的两个端点。

【输出格式】

一行若干个整数,从小到大输出最上面的线段的编号。

5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
2 4 5
3
0 0 1 1
1 0 2 1
2 0 3 1
1 2 3