计算几何：凸包提高组

💡 核心思想

凸包是包含给定点集的最小凸多边形。Graham 扫描法：先选一个最左下角的点作为基准，按极角排序其他点，然后用单调栈维护凸包边界，逐个检查新点是否使凸包"凹"进去，如果是则弹出栈顶点。Andrew 算法：按 x 坐标排序，分别构造下凸壳和上凸壳，最后合并。Andrew 算法更稳定，避免了极角排序的精度问题。

🎯 直觉理解

想象你在地上钉了一堆钉子，然后用一根橡皮筋套住所有钉子。橡皮筋绷紧后形成的形状就是凸包——它把所有钉子都包在里面，而且形状是"凸"的（没有凹陷）。Andrew 算法就像用两只手从左右两边向中间"捏"，把外层的点依次抓出来。

📝 算法流程

1. Andrew 算法：
2. 按 x 坐标排序（x 相同则按 y）
3. 构造下凸壳：从左到右遍历，用栈维护
4. 如果栈中点数 >= 2 且 cross(倒数第二点, 栈顶, 当前点) <= 0，弹出栈顶
5. 当前点入栈
6. 构造上凸壳：从右到左遍历，同样用栈维护
7. 合并下凸壳和上凸壳（去掉重复端点）

$$\text{叉积：} \vec{OA} \times \vec{OB} = x_A y_B - x_B y_A$$

$$\text{凸包周长：} \sum_{i=0}^{m-1} |P_i P_{(i+1) \bmod m}|$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

struct Point {
    double x, y;
    bool operator<(const Point& o) const {
        return x < o.x || (x == o.x && y < o.y);
    }
};

double cross(const Point& o, const Point& a, const Point& b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

vector convexHull(vector& pts) {
    sort(pts.begin(), pts.end());
    int n = pts.size();
    if (n <= 1) return pts;
    
    vector lower, upper;
    for (int i = 0; i < n; i++) {
        while (lower.size() >= 2 && 
               cross(lower[lower.size()-2], lower.back(), pts[i]) <= 0)
            lower.pop_back();
        lower.push_back(pts[i]);
    }
    for (int i = n - 1; i >= 0; i--) {
        while (upper.size() >= 2 && 
               cross(upper[upper.size()-2], upper.back(), pts[i]) <= 0)
            upper.pop_back();
        upper.push_back(pts[i]);
    }
    
    lower.pop_back();
    upper.pop_back();
    lower.insert(lower.end(), upper.begin(), upper.end());
    return lower;
}

int main() {
    vector pts = {{0,0}, {1,1}, {2,2}, {2,0}, {2,1}, {1,0}};
    auto hull = convexHull(pts);
    for (auto& p : hull) cout << "(" << p.x << "," << p.y << ") ";
    cout << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目