BZOJ 1007 [HNOI2008] 水平可见直线


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

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

n≤5*104


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

代码如下:

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1007 [HNOI2008] 水平可见直线


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,