【bzoj1007】[HNOI2008]水平可见直线

2014年2月24日4,4155

Description

Input

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

Output

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

Sample Input

3
-1 0
1 0
0 0

Sample Output

1 2

题解

算法比较直观,先按斜率排序,再将最小的两条线入栈,然后依次处理每条线,如果其与栈顶元素的交点在上一个点的左边,则将栈顶元素出栈 ;这样为什么对呢?因为对如任意一个开口向上的半凸包,从左到右依次观察每条边和每个顶点,发现其斜率不断增大,顶点的横坐标也不断增大。

 

  • hzy98192015年11月29日 上午11:46 回复

    黄学长刷的题好多。。但学长表示800道题足够进队了

    #1  
    • hzwer2015年11月29日 下午2:24 回复
      admin

      以前学长和我说bzoj100题就能进队。。。这是命吧

      #11
  • 凹凸凹凸2015年11月29日 上午11:54 回复

    擦,有人冒充我

    #2  
  • Erbhj2016年1月11日 下午3:03 回复

    为什么crossx(a,st[top-1])<=crossx(st[top],st[top-1])可以判断交点在左边?

    #3  
    • Sundes2016年3月31日 上午9:52 回复

      crossx求出两直线方程关于x的解.. 根据x坐标的大小就可以判断左右呀.

      #31