93 #P1212. G50 叉积应用 线线关系*【计算几何:叉积】判断线段相交[POJ2653]
G50 叉积应用 线线关系*【计算几何:叉积】判断线段相交[POJ2653]
【题意】
有 条线段(编号为 ~ ),按 ~ 的顺序放在二维坐标系上(先放1号线段,再放2号线段 …… )。
要求输出最上面的那些线段的编号(就是没有其他线段压在它上面的那些线段)。
【输入格式】
第一行一个数 ( )。
下来 行,每行两个坐标,表示第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