二维凸包

模板题（luogu.P2742）

凸包定义

给定二维平面上的点集 \(P\)，定义能包含这些点的最小凸多边形为 \(P\) 的凸包。

形象地说，凸包就是一根橡皮筋拉伸，使其包括了点集 \(P\) 中所有点，然后使橡皮筋收紧，橡皮筋就是 \(P\) 的凸包。

例如，下面用红色线段表示了一个点集的凸包（原创图）：

凸壳定义

将点集 \(P\) 的凸包分为上下两部分，称为上凸壳、下凸壳，使得任意一条与 \(y\) 轴平行的直线都与上、下凸壳最多只有一个交点。

这是一个点集的上凸壳（原创图）：

这是一个点集的下凸壳（原创图）：

求解凸包

显然，可以求出上、下凸壳，然后就得到了凸包。

先考虑求下凸壳。

有两个显然的性质：

1. 同一个下凸壳上的线段斜率随 \(x\) 坐标的增大单调不减。

2. \(x\) 坐标最大的点一定在下图壳上。

利用这两个性质，就可以增量法求下凸壳：

1. 将所有点以 \(x\) 坐标排序，去重。

2. 依次加入每个点，用栈记录当前下凸壳中所有点，令当前加入点 \(p\)。

3. 若当前凸壳中点数小于 \(2\)，直接加入 \(p\)。

4. 否则令当前下凸壳 \(x\) 坐标最大的两个点为 \(p_1,p_2\)，令一个点 \(p_k\) 的 \(x\) 坐标为 \(x(p_k)\)，\(y\) 坐标为 \(y(p_k)\)：

• 若线段 \(p_1 p_2\) 的斜率大于线段 \(p_2 p\) 的斜率，也就是这种情况（原创图）：

  

  因为 \(x\) 坐标最大的是点 \(p\)，因此它一定在下凸壳中，为了保证下凸壳的性质，点 \(p_2\) 只能不属于下凸壳，弹栈。

  

  然后重复此过程直到 \(p_2 p\) 为下凸壳中斜率最大的线段。

求上凸壳同理。