二维凸包与旋转卡壳 (Convex Hull & Rotating Calipers)¶

凸包（Convex Hull） 是计算几何中最核心的基础结构之一。

形象地说，在一个平面点集上方用一根橡皮筋将所有点紧紧包裹起来，橡皮筋所形成的封闭凸多边形就是该点集的凸包。凸包不仅具有极佳的几何性质，更是求解平面最远点对（凸包直径）、最小外接矩形、多边形相交与半平面交的前置步骤。

1. 凸包的定义与几何性质¶

1.1 数学定义¶

对于平面点集 \(S\)，其凸包 \(\text{CH}(S)\) 定义为包含 \(S\) 的最小凸多边形，亦即包含 \(S\) 的所有凸集的交集。

核心几何性质：¶

极值点性质：凸包的顶点必属于原点集 \(S\)；
支撑超平面性质：经过凸包任意顶点的切线，使得整个点集 \(S\) 完全位于该切线的同侧；
周长与面积最小性：在所有包含点集 \(S\) 的凸多边形中，凸包的周长最小，面积最小。

2. Andrew 算法 (Monotone Chain)¶

求解二维凸包的算法有 Graham 扫描法（极角排序）和 Andrew 算法（水平序单调链）。

在实际工业界和算法竞赛中，Andrew 算法是绝对的首选：

它不需要计算角度或调用 atan2，完全依赖坐标双关键字排序与整数叉积；
数值稳定性极高，代码极其简练，时间复杂度为严格最优的 \(\mathcal{O}(N \log N)\)。

2.1 算法详细流程¶

Andrew 算法两阶段单调栈推进：
1. 排序: 按 X 升序, 若 X 相同按 Y 升序排序
2. 构造下凸壳 (从左到右):
   遍历每个点, 若新点在栈顶两点连线的右侧 (叉积 < 0), 弹出栈顶;
3. 构造上凸壳 (从右到左):
   从倒数第二个点开始反向遍历, 同样维护单调栈;

执行步骤：¶

双关键字排序：将所有点按 \(x\) 坐标升序排序；若 \(x\) 相同，按 \(y\) 坐标升序排序；
求下凸壳（Lower Hull）：
维护一个点栈 stk；
从前往后遍历每个点 \(P_i\)：
- 当栈中至少有 2 个点时，设栈顶为 \(B\)，栈顶下方为 \(A\)；
- 若向量 \(\vec{AB} \times \vec{AP_i} < 0\)（说明向右偏转，破坏了凸性），则将 \(B\) 弹出栈；
- 重复此过程，直到满足凸性或栈中少于 2 个点；
- 将 \(P_i\) 压入栈中；
求上凸壳（Upper Hull）：
记录当前下凸壳的点数 \(t = stk.size()\)；
从后往前倒序遍历每个点 \(P_i\)：
- 重复相同的叉积单调性检验（但只检查新增在上凸壳中的点，即栈中元素个数 \(> t\)）；
- 将 \(P_i\) 压入栈中；
栈底点在闭合时会被重复压入一次，弹出最后一个重复点即可。

2.2 边界共线点处理技巧 (LeetCode 587 深度避坑)¶

在标准凸包定义中，凸包边上的共线点通常会被剔除（只保留凸包顶点）。但在 LeetCode 587 (安装栅栏) 中，要求必须输出凸包边界上的所有点（包括共线点）！

关键改动：¶

叉积判定符号：
若不保留共线点：cross(B - A, P - A) <= 0 时弹出栈顶（共线点叉积为 0，也会被弹出）；
若严格保留共线点：cross(B - A, P - A) < 0 时才弹出栈顶（共线点叉积为 0，得以保留）；
used 访问标记数组：
使用 used[i] 记录点 \(i\) 是否已在下凸壳中。构造上凸壳时，已经作为下凸壳严格内部点的元素不可复用，但起点和终点必须能够被上凸壳复用；
在弹栈时必须将 used[pop_idx] = false，恢复未选用状态。

2.3 工业级 C++ 凸包模板 (支持共线点)¶

#include <vector>
#include <algorithm>

struct Point {
    int x, y;
    int id; // 原始下标
};

long long cross(const Point& O, const Point& A, const Point& B) {
    return 1LL * (A.x - O.x) * (B.y - O.y) - 1LL * (A.y - O.y) * (B.x - O.x);
}

// Andrew 算法求凸包 (包含边界共线点)
std::vector<Point> getConvexHullWithCollinear(std::vector<Point>& pts) {
    int n = pts.size();
    if (n <= 3) return pts;

    // 1. 坐标双关键字升序排序
    std::sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });

    std::vector<Point> hull;
    std::vector<bool> used(n, false);

    // 2. 构造下凸壳
    for (int i = 0; i < n; ++i) {
        while (hull.size() >= 2 && cross(hull[hull.size() - 2], hull.back(), pts[i]) < 0) {
            used[hull.back().id] = false;
            hull.pop_back();
        }
        hull.push_back(pts[i]);
        used[i] = true;
    }

    // 3. 构造上凸壳
    used[0] = false; // 允许首点闭合
    int t = hull.size();
    for (int i = n - 2; i >= 0; --i) {
        if (used[i]) continue;
        while (hull.size() > t && cross(hull[hull.size() - 2], hull.back(), pts[i]) < 0) {
            used[hull.back().id] = false;
            hull.pop_back();
        }
        hull.push_back(pts[i]);
        used[i] = true;
    }

    hull.pop_back(); // 移除首末重复点
    return hull;
}

3. 旋转卡壳 (Rotating Calipers)¶

旋转卡壳（Rotating Calipers） 由 Michael Shamos 于 1978 年发明，是一种在求出凸包后，以严格 \(\mathcal{O}(N)\) 线性时间求解凸包直径（最远点对距离）、最小外接矩形、凸多边形间最小距离的高阶算法。

3.1 核心思想：对踵点对 (Antipodal Pairs)¶

如果两条平行的公切线夹住凸多边形，切线与凸包相交的点对称为对踵点对（Antipodal Pair）。

凸包直径定理：平面点集的最远点对，必然是该点集凸包的某一对对踵点！

旋转卡壳双指针推进示意：
        切线 L_1 ---------> 逆时针旋转
         / \
        /   \ 
       /     \  凸包
      /       \
      ---------
        切线 L_2 ---------> 同步逆时针旋转

3.2 算法执行：面积单峰性双指针¶

对于凸包上的一条固定底边 \(P_i P_{i+1}\)，点 \(P_k\) 到该底边的距离与其构成的三角形面积 \(\text{Area}(P_i, P_{i+1}, P_k)\) 成正比。

因为凸包具有严格凸性，当 \(k\) 沿逆时针方向移动时，三角形面积呈现严格单峰函数（先增后减）！

因此，当底边 \(i\) 沿逆时针前进时，使得距离最大的对踵点 \(k\) 也必定沿逆时针方向单调前进。利用双指针（尺取法），底边遍历一圈 \(\mathcal{O}(N)\)，对踵点指针总共也只旋转一圈 \(\mathcal{O}(N)\)，从而在 \(\mathcal{O}(N)\) 内求出全局最远点对！

4. LeetCode 经典真题精选与深度精析¶

LeetCode 587 - 安装栅栏 (Erect the Fence) 困难
提示

二维凸包 Andrew 算法标准应用（含共线点）。
- 题目明确要求包含栅栏边界上的所有树木（即凸包边缘的共线点必须全量保留）。
- 详见本文 2.2 节深度解析。
- 将弹出条件从 <= 改为严格 <，并在回退时正确恢复 used 标记。
- 闭合后去重输出所有点。时间复杂度 \(\mathcal{O}(N \log N)\)，空间复杂度 \(\mathcal{O}(N)\)。