【BZOJ 1007】【HNOI 2008】水平可见直线 【计算几何】
题目跳转: http://www.lydsy.com/JudgeOnline/problem.php?id=1007
Description
在xoy直角坐标平面上有n条直线L1,L2,…Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为
可见的,否则Li为被覆盖的.
例如,对于直线:
L1:y=x; L2:y=-x; L3:y=0
则L1和L2是可见的,L3是被覆盖的.
给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.
Input
第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi
Output
从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格
Sample Input
3
-1 0
1 0
0 0
Sample Output
1 2
题解
解法一: 单调栈[1]
我们考虑先把Line按照双关键字排序。（没找到图，请自己画）
第一关键字肯定是斜率，第二关键字是截距。
我们考虑将斜率升序(降序也可以),然后截距降序。（显然，斜率相同的截距低的一定不用考虑。）