Re：从零开始的动态凸壳

动态凸包概述

动态凸包（Dynamic Convex Hull）问题是指在二维平面上，维护一个点集的凸包结构，并支持在点集中动态地插入或删除点，同时能够高效地查询当前凸包的状态或属性（如周长、面积、顶点集合等）。该问题在计算几何、计算机图形学、机器人路径规划、动态规划等领域具有广泛应用。

前置知识

向量

先看 百度百科 & oi-wiki。

定义 1

向量向量顾名思义是具有方向（向）和大小（量）的量，通常使用有向线段（带箭头的线段）表示，如下图：

表示

向量有三种表示方法，如下图的向量：

其可表示为：

• \(\vec a\)；
• \(\vec{AB}\)；
• \((-2.5,1)\)。

其中第三种被称为向量的坐标表示。向量的坐标为终点坐标减起点坐标。

定义 2

如两向量方向相反称这两向量互为相反向量记作 \(\vec v = - \vec u\)。

运算

加减

向量的加法可以看成是一段连续位移的叠加，如图：其中 \(\vec v + \vec u = \vec w\)，这种加法法则被称为三角形法则。
由此引申可得平行四边形法则，如图：其中 \(\vec v \mathop{//} f, \vec u \mathop{//} g, \vec v + \vec u = \vec w\)。

向量的减法可以看作加法的逆运算，例如 \(\vec v - \vec u = \vec w\) 表示从 \(\vec v\) 中减去 \(\vec u\) 的效果，等价于 \(\vec v + (-\vec u)\)。

容易得到向量加减的坐标运算为 \((x,y)\pm(a,b)=(x\pm a,y\pm b)\)。

模

向量模为向量的长度，符号与绝对值相同，如图：

其中 \(\left | \vec u \right | = \frac{\sqrt{29}}{2}\)。

容易得到向量的模的坐标运算为 \(\left | (a,b) \right | = \sqrt{a^2+b^2}\)。

定义 3

模为 \(1\) 的向量为单位向量，一般用 \(\vec e\) 表示。

叉乘

在二维空间中，向量的叉乘表示两个向量构成的平行四边形的有向面积，如图：其中 \(\vec w \times \vec v = S_a = -2.25\)。可以得到 \(\vec w \times \vec v = |w||v|\sin<w,v>\)。

可以得到叉乘的坐标运算为 \((a,b)\times(x,y)=ay-bx\)。

证明：
设 \(x\) 轴的单位向量为 \(\vec e_1\)，\(y\) 轴的为 \(\vec e_2\)。\((a,b)\times(x,y) = (a\vec e_1 + b\vec e_2)\times(x\vec e_1 + y\vec e_2)\)。
展开得 \(a x \vec e_1 \times \vec e_1 + a y \vec e_1 \times \vec e_2 + b x \vec e_2 \times \vec e_1 + b y \vec e_2 \times \vec e_2\)。
由于 \(\vec e_1 \times \vec e_1 = 0\)，\(\vec e_2 \times \vec e_2 = 0\)，且 \(\vec e_1 \times \vec e_2 = -\vec e_2 \times \vec e_1 = 1\)（\(\vec e_1\perp\vec e_2\)）。
化简得 \(a y - b x\)，得证。

叉乘符号则表示两个向量的相对方向关系：

• 若结果为正，表示第二个向量在第一个向量的逆时针方向；
• 若结果为负，表示第二个向量在第一个向量的顺时针方向；
• 若结果为 0，说明两向量共线。

凸包

先看 百度百科 &oi-wiki。

定义一

在平面上能包含所有给定点的最小凸多边形叫做凸包。

如图：

其中蓝色多边形为凸包：

实际上可以理解为用一个橡皮筋包含住所有给定点的形态。

定义二

凸包中相邻的边若斜率愈来愈大则称下凸壳，相邻的边若斜率愈来愈小称上凸壳。

Andrew's Monotone Chain 算法

以下来自 oi-wiki。

该算法的时间复杂度为 \(O(n \log n)\)，其中 \(n\) 为待求凸包点集的大小。复杂度的瓶颈在于对所有点坐标的双关键字排序。
具体过程如下：

1. 排序：
   将所有点以横坐标为第一关键字、纵坐标为第二关键字进行升序排序。排序后，最小和最大的元素一定在凸包上。
2. 构造凸壳：
   利用单调栈维护凸壳。由于上下凸壳旋转方向不同，先升序枚举构造下凸壳，再降序枚举构造上凸壳。
3. 判断方向：
   从栈顶取出两个点 \(S_1\)、\(S_2\)（其中 \(S_1\) 为栈顶），若即将入栈的点 \(P\) 与这两个点构成的方向为右拐（即叉积小于 0）：\(\vec{S_2S_1} \times \vec{S_1P} < 0\) 则弹出栈顶 \(S_1\)，重复此过程直到满足：\(\vec{S_2S_1} \times \vec{S_1P} \leq 0\) 或栈中只剩一个元素为止。
4. 保留边界点（可选）：
   若需保留凸包边界上的点，可将上述条件中的 < 改为 ≤，相应地将反向判断条件 > 改为 ≥。
   最终将上下凸壳合并，即可得到完整的凸包。

code

点击查看代码

// stk[] 是整型，存的是下标
// p[] 存储向量或点
tp = 0;                       // 初始化栈
std::sort(p + 1, p + 1 + n);  // 对点进行排序
stk[++tp] = 1;
// 栈内添加第一个元素，且不更新 used，使得 1 在最后封闭凸包时也对单调栈更新
for (int i = 2; i <= n; ++i) {while (tp >= 2  // 下一行 * 操作符被重载为叉积&& (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0)used[stk[tp--]] = 0;used[i] = 1;  // used 表示在凸壳上stk[++tp] = i;
}
int tmp = tp;  // tmp 表示下凸壳大小
for (int i = n - 1; i > 0; --i)if (!used[i]) {// ↓求上凸壳时不影响下凸壳while (tp > tmp && (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0)used[stk[tp--]] = 0;used[i] = 1;stk[++tp] = i;}
for (int i = 1; i <= tp; ++i)  // 复制到新数组中去h[i] = p[stk[i]];
int ans = tp - 1;

正文 —— Andrew's Monotone Chain 算法变种

现在考虑已经有一个凸壳（为了方便讲解，以上凸壳为例），如下图：

现在考虑插入一个点，分两种情况讨论：

情况一：点在凸壳下或在凸壳上

如图：
若 \(G\) 为插入点，\(C\) 为插入点在凸包中的前驱（\(x\) 为第一关键字，\(y\) 为第二关键字排序），\(D\) 为插入点在凸包中的后继，设 \(\vec{OG} = \vec u, \vec{OC} = \vec v, \vec{OD} = \vec w\)，可得 \((\vec v - \vec u) \times (\vec w - \vec u) \le 0\)，如图：

证明：根据向量叉乘的几何意义，\(\vec{GC} \times \vec{GD}\) 的结果表示以 \(GC\) 和 \(GD\) 为邻边的平行四边形的有向面积。若该值 \(\leq 0\)，则说明向量 \(\vec{GD}\) 位于向量 \(\vec{GC}\) 的顺时针方向或共线。
设 \(C\)、\(D\) 为插入点 \(G\) 在凸包中的前驱和后继（按 \(x\) 坐标排序），则凸包上 \(C\) 到 \(D\) 的线段是上凸壳的一部分，其斜率单调递减（上凸壳的性质）。若 \(G\) 在凸包下方或凸包上，则 \(G\) 必须位于线段 \(CD\) 的下方或线段上。此时，线段 \(GC\) 的斜率 \(k_1\) 必然大于等于线段 \(GD\) 的斜率 \(k_2\)（即 \(k_1 \geq k_2\)），否则 \(G\) 会位于凸包外部，导致原凸包不再是“最小凸多边形”。
根据叉乘的坐标运算：
设 \(G(x_0,y_0)\)，\(C(x_1,y_1)\)，\(D(x_2,y_2)\)，则：\(\vec{GC} = (x_1-x_0, y_1-y_0)\)，\(\vec{GD} = (x_2-x_0, y_2-y_0)\)，\(\vec{GC} \times \vec{GD} = (x_1-x_0)(y_2-y_0) - (x_2-x_0)(y_1-y_0)\)
若 \(k_1 \geq k_2\)，即 \(\frac{y_1-y_0}{x_1-x_0} \geq \frac{y_2-y_0}{x_2-x_0}\)（假设 \(x_1 < x_0 < x_2\)，分母为正），交叉相乘得：\((y_1-y_0)(x_2-x_0) \geq (y_2-y_0)(x_1-x_0)\)
移项后：\((x_1-x_0)(y_2-y_0) - (x_2-x_0)(y_1-y_0) \leq 0\)
即 \(\vec{GC} \times \vec{GD} \leq 0\)。

此时容易发现，这个点不可能改变凸壳。

情况二：点在凸壳上

如图：

此时容易发现，这个点会改变凸壳。
于是我们向左右两边更新凸壳，具体如下。

更新左端

每次我们取出加入点（设为 \(G\)）在凸壳中的前驱（设为 \(C\)）以及前驱的前驱（设为 \(B\)）。若 \(BC\) 相对与 \(BG\) 顺时针旋转，即 \(\vec{BC} \times \vec{BG} \ge 0\)，则删除 \(C\)（在 \(G\) 加入之后 \(C\) 若在凸壳上则不满足凸壳的性质），如图：

\(\begin{matrix}\Huge\Longrightarrow\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \end{matrix}\)