BZOJ_1007 水平可见直线

1.题目相关

2.思路

  • 先介绍一个概念:


    2-1 左边是上凸壳,右边是下凸壳
  • 这题显然是要维护一个上凸壳。
  • 首先把直线按照斜率为第一关键字,截距为第二关键字排序。
  • 搞一个以斜率为关键字的单调栈,单调栈记录的就是当前的上凸壳。
  • 算出将入栈的直线与top的交点 X1 和 top 与 top-1 两条直线的交点 X2。
  • 若 X1 <= X2 则将 top 弹出。

点击查看代码

引用

2-1:http://www.cnblogs.com/BLADEVIL/archive/2013/12/12/3470781.html

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容