1.题目相关
-
标签：
半平面交 - 题目地址：http://www.lydsy.com/JudgeOnline/problem.php?id=1007
- 题目大意：见原题。
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
