BZOJ 1007 [HNOI2008] 水平可见直线

发布于 2017-04-18  194 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1007

题意:给出 n 条直线的解析式,在坐标系上从上向下看,问能看到哪些直线。

n≤5*104


做法是这样的... 对于每一条边,按照斜率排序,排序后依次入栈,若当前入栈直线与栈顶直线的交点在上一个点的左边,很显然,栈顶被覆盖了。

代码如下:

 


一个非常弱的准退役OIER