半平面交

概述

一条有向直线左侧的区域称为半平面，通常用边界直线上一点加方向向量表示。多个半平面的交是一块凸区域，可能为空、无界或退化，常用来求线性规划可行域或多边形的核。主流的 S&I 算法把所有半平面按方向向量的极角排序，再用一个双端队列维护当前交的边界：加入新半平面时，从队尾、队首依次弹出被它切掉的旧边界，然后把它压入队列。整体复杂度 O(nlogn)，瓶颈落在排序上。文末给出一道求多边形核的例题。

参考资料

• 半平面交 - OI Wiki

简介

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

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

例题

洛谷 P4196 【模板】半平面交 / [CQOI2006] 凸多边形

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