当前位置: 代码迷 >> 综合 >> bzoj1007: [HNOI2008]水平可见直线
  详细解决方案

bzoj1007: [HNOI2008]水平可见直线

热度:11   发布时间:2023-10-29 09:54:32.0

前言

翘课翘了一下午,什么都没做
今天发现在做某道题的时候发现在不会做
然后发现有人同1007
于是回去看。。发现我做过但是忘了

题解

先按斜率从小到大排序,再将斜率最小的两条直线入栈。
对于每条直线,如果其与栈顶直线的交点在上一个点的左边
就将栈顶直线出栈
我们现在来尝试理解一下
对于两条直线l1,l2
前者的斜率大于后者
那么l1漏出来的地方肯定是在交点右边的,被覆盖的是在交点左边的
然后如果你现在假如一条直线l3,如果他的交点在这个交点的左边,那么就意味着他右边也被覆盖了。那么他就看不见了

以上