凸包

凸包相关内容。

---

前置芝士

凸多边形

凸多边形指的是所有内角都在 $(0,\pi]$ 范围内的多边形。

凸包

对于一个平面上的一个给定的点集，他们对应的凸包就是能把他们全部包含的最小凸多边形。

如果形象一点，可以把平面上的点集想象成木板上的钉子，而其对应的凸包则是一根将所有点围在内部的橡皮筋。

凸包求法

常用的凸包求法有Graham扫描法和Andrew算法，这里主要讲解Graham扫描法，Andrew算法可以看OI-Wiki对应内容。

复杂度

Graham扫描法的时间复杂度是 $O(n \log n)$，瓶颈主要在对所有点的极角排序上。

过程

选取基准点

首先我们选择一个点来当做我们的基准点。
这个点需要在整个点集的最下方，而如果有多个纵坐标相同的点我们选横坐标最小的点，所以我们直接 $O(n)$ 扫一遍即可。

极角排序

然后把剩下的点以刚才我们选出的点为基准进行极角排序。
因为这个点的左下方没有点，那么任意一个点的极角只能在 $(0,\pi]$ 范围内。
会的可以跳过。

下面将我们目前需要比较的两个点称作 $P_i$ 和 $P_j$，将基准点称为 $P_0$。

我们可以选择两种方法来进行排序。

首先是一种比较浅显的，通过极角的余弦值的相反数来排序。
通过观察，我们可以发现在 $(0,\pi]$ 范围内，函数 $f(x)=-\cos(x)$ 是单调递增的。
所以我们如果知道了 $-\cos(\angle P_i P_0 x) < -\cos(\angle P_j P_0 x)$，那就可以推出来 $\angle P_i P_0 x < \angle P_j P_0 x$。

代码如下：

double dis(Point a, Point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool cmp(Point lhs, Point rhs)
{
    double lang = -((lhs.x - p[b].x) / dis(lhs, p[b]));
    double rang = -((rhs.x - p[b].x) / dis(rhs, p[b]));
    if(lang - rang == 0)return dis(lhs, p[b]) < dis(rhs, p[b]);
    else return lang < rang;
}

或者是构造出来两个向量，通过向量的叉积来判断两者的位置。

我们构造出来两个向量 $\overrightarrow{P_0 P_i}$ 和 $\overrightarrow{P_0 P_j}$，然后计算出来两个向量的叉积。
如果叉积为正，那么就可以证明 $\angle P_i P_0 x < \angle P_j P_0 x$。

代码如下：

double dis(Point a, Point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double oprod(Point a, Point b, Point c, Point d)
{
    return (b.x - a.x) * (d.y - c.y) - (d.x - c.x) * (b.y - a.y);
}
bool cmp(Point lhs, Point rhs)
{
    double chq = oprod(p[b], lhs, p[b], rhs);
    if(chq == 0)return dis(lhs, p[b]) < dis(rhs, p[b]);
    else return chq > 0;
}

构建凸包

首先来一个图来演示一下构建凸包的过程：

我们使用一个栈来维护当前在凸包上的点。

首先，我们将基准点和第一个点无条件加入栈中。

然后，我们遍历剩下的点，每一次将将要加入栈中的点 $P$ 与栈顶的点 $S_1$ 和栈顶下方的第一个点 $S_2$ 构成两个向量 $\overrightarrow{S_1 P}$ 和 $\overrightarrow{S_2 S_1}$，如果 $\overrightarrow{S_1 P}$ 较 $\overrightarrow{S_2 S_1}$ 向顺时针方向旋转，即叉积 $\overrightarrow{S_1 P} \times \overrightarrow{S_2 S_1} < 0$，我们就将 $S_1$ 弹出栈，返回上一步继续检测，直到栈中只剩一个点或叉积非负为止。
最后把点加入栈中。

当我们顺序遍历完所有点之后，栈中会留下一些点。
把相邻的点两两连边之后形成的封闭多边形就是我们的凸包。

代码如下：

vector<Point>v;
for(int i = 1; i <= n; i++)
    if(i != b)v.push_back(p[i]);
sort(v.begin(), v.end(), cmp);//稍微麻烦一点的排序
p[1] = p[b];
for(int i = 2; i <= n; i++)
    p[i] = v[i - 2];
sta[1] = 1, sta[2] = 2, tt = 2;//初始化栈
for(int i = 3; i <= n; i++)
{
    while(tt >= 2 && oprod(p[sta[tt - 1]], p[sta[tt]], p[sta[tt]], p[i]) <= 0)
        tt--;
    sta[++tt] = i;
}