AC. 梦想

frank_c1

[BZOJ 1007] 水平可见直线

发布于2015年12月21日 | 暂无评论 | 560阅读 | 计算几何

题目描述

在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条直线两两不重合。求出所有可见的直线。

输入格式

第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi。

输出格式

从小到大输出可见直线的编号,两两中间用空格隔开,最后一个数字后面也必须有个空格。

题目解析

计算几何基础半平面交。先按照直线的斜率为第一关键字,截距为第二关键字排序。然后维护一个栈,如果将要入栈的元素与栈顶元素的交点在前一个交点的左边,那么栈顶元素一定可以丢掉。最后留在栈中的元素就是所谓水平可见直线,复杂度O(n \log n)