半平面交

参考资料

一条有向直线左侧的区域称为一个 半平面。多个半平面的交是一个凸区域（可能为空、无界或退化），常用来求可行域或多边形的核。

S&I 算法：把所有半平面按其方向向量的极角排序，用一个双端队列维护当前交的边界；加入新半平面时，从队尾、队首弹出被它「切掉」的旧边界，再入队。整体复杂度 $O(n\log n)$ ，瓶颈在排序。

给定若干个凸多边形，求它们公共部分（仍是一个凸多边形）的面积。