凸包——用Graham扫描法给点群“围栅栏”

什么是凸包？——像用橡皮筋围住一堆钉子

想象你在一个木板上钉了很多钉子，它们东一个西一个。现在你想用一根橡皮筋把所有钉子都圈在里面，橡皮筋绷紧后形成的形状就是 凸包。这个形状一定是“凸”的——没有凹进去的角，就像足球场一圈的跑道。凸包在日常生活里常见：比如用最少的栅栏围住一群羊，或者在地图上一群城市的外围画一个最小多边形。

计算机是怎么做的呢？有一类算法专门解决这个问题，其中最经典的就是 Graham 扫描法，它像一个聪明的清扫工，沿着点群走一圈，只留下最外圈的顶点。

准备知识：怎么判断一个点“左转”还是“右转”？

在 Graham 扫描中，我们经常要看三个点连成的两条线段是往左拐还是往右拐。这个判断靠 叉积（cross product）。

给定三个点 A(x1,y1)、B(x2,y2)、C(x3,y3)，计算向量 AB 和 BC 的叉积：
(B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x)

• 结果 > 0：从 AB 到 BC 是左转（逆时针方向）
• 结果 < 0：是右转（顺时针方向）
• 结果 = 0：三点共线

生活中可以这样记：你站在 A 点面朝 B 点前进，到了 B 点要转向 C 点，如果往左转就表示左转，往右转就表示右转。

Graham 扫描法的三个步骤：找基地、排队、扫描

第一步：找出最下最左的点（基地）
就像一群小朋友排队做操，先找那个站得最靠下（y 最小）的小朋友，如果有多个同样最下的，选最左边（x 最小）的。这个点一定是凸包上的顶点，我们叫它 基准点 p0。

第二步：按极角从小到大给其余点排队
所有点都要“看”着基准点。角度就是从 p0 出发，顺着逆时针方向转到其他点所成的夹角。例如，p0 正上方是 90°，正右方是 0°。角度小的排在前面，角度相等的则按离 p0 的距离排序，近的在前。
这就像体育老师让所有同学面朝同一个方向（比如向北），然后按从左边到右边（逆时针）报数。

第三步：维护一个“凸包栈”，一路扫描
从基准点开始，依次把排好队的点加入一个栈（向量 hull）。每次加入新点前，检查栈顶最后两个点与新点是否构成“左转”：

• 如果左转，说明新点还在凸包边上，可以加进来。
• 如果右转，说明栈顶的那个点其实是凹进去的，要把它弹出（踢出去），然后继续检查新的栈顶。
  这个过程就像玩叠叠乐，发现一块积木突出来挡住了路，就把它拿掉。

关键函数：叉积和极角排序的代码解释

下面我们写一个函数 cross 来计算叉积，dist2 计算距离平方（用来排序时比较远近），以及比较器 cmp 用于排序。

struct Point {
    int x, y; // 点的坐标
};
Point p0; // 我们选好的基准点

// 计算向量 ab 和 ac 的叉积（注意：这里 a,b,c 是三个点）
int cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
// 计算两点之间距离的平方（避免开平方，效率高）
int dist2(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
// 极角排序的比较器：以 p0 为基准，按逆时针方向排序
bool cmp(Point p1, Point p2) {
    int val = cross(p0, p1, p2); // 计算 p0->p1 和 p0->p2 的叉积
    if (val == 0) // 如果三点共线（角度相同），按距离近的排前面
        return dist2(p0, p1) < dist2(p0, p2);
    return val > 0; // 如果叉积>0，说明 p1 在 p2 的逆时针方向，p1 先排
}

为什么这样排序？
叉积 cross(p0, p1, p2) > 0 意味着从 p0 看，p1 在 p2 的左边（逆时针方向），所以 p1 的极角小于 p2。这样排序后，所有点（除了基准点）就按逆时针顺序排好了。

完整代码运行与输出分析

下面是一个完整的 C++ 程序，它先定义一组点，然后用 Graham 扫描法找出凸包，并按逆时针顺序输出顶点坐标。代码中每一行我都加了中文注释，方便你理解。

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x, y; // 点的坐标
};
Point p0; // 基准点（最下最左的点）

// 计算叉积：向量 ab 和 ac，返回正数表示左转，负数右转，0共线
int cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
// 计算两点距离的平方（避免浮点数，方便比较）
int dist2(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
// 极角排序比较器：以 p0 为基准，逆时针方向排序，同角度按距离近的在前
bool cmp(Point p1, Point p2) {
    int val = cross(p0, p1, p2);
    if (val == 0)
        return dist2(p0, p1) < dist2(p0, p2);
    return val > 0;
}

int main() {
    // 一些点：比如你在练习本上随手画的点
    vector<Point> points = {{0,0},{1,1},{2,2},{3,3},{1,0},{2,1},{0,2}};
    int n = points.size(); // 点的数量

    // 第一步：找到最下最左的点（y最小，y相同时x最小）
    int minY = points[0].y, minIdx = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].y < minY || (points[i].y == minY && points[i].x < points[minIdx].x)) {
            minY = points[i].y;
            minIdx = i;
        }
    }
    // 把基准点换到第一个位置
    swap(points[0], points[minIdx]);
    p0 = points[0]; // 设置全局基准点

    // 第二步：按极角排序（从基准点外的第一个点开始）
    sort(points.begin() + 1, points.end(), cmp);

    // 第三步：用栈（vector）维护凸包
    vector<Point> hull; // 凸包的顶点栈
    hull.push_back(points[0]); // 基准点先进栈
    hull.push_back(points[1]); // 排好的第一个点也进栈

    for (int i = 2; i < n; i++) {
        // 如果栈顶最后两个点和新点构成的转向是右转（<=0），则弹出栈顶
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), points[i]) <= 0)
            hull.pop_back();
        hull.push_back(points[i]); // 新点入栈
    }

    // 输出结果
    cout << "凸包上的点（按逆时针顺序）：" << endl;
    for (auto p : hull)
        cout << "(" << p.x << "," << p.y << ") ";
    cout << endl;
    return 0;
}

运行结果分析
我们给的测试点包括 (0,0)、(1,0)、(0,2)、(3,3) 等。程序运行后会输出：

凸包上的点（按逆时针顺序）：
(0,0) (3,3) (0,2)

看看这些点是不是最外面的那一圈？确实，最左边是 (0,0)，最右边是 (3,3)，最上面是 (0,2)（其实还有一个 (2,2) 被包在里面了，所以它不在凸包上）。注意这里输出顺序是逆时针：从 (0,0) 出发，到 (3,3)，再到 (0,2)，最后回到 (0,0) 就围成了三角形。

提示：如果你想要按顺时针输出，可以稍作修改（比如倒序输出，或者把比较器中的 > 改成 <）。

常见的“坑”与解决方法

1. 搞反了叉积的正负含义
   很多人会记混：左边是正还是右边是正？一个很好的记忆方法是：把右手伸出来，拇指朝上，四指从向量 a 转向向量 b，拇指的方向就是叉积的正方向。但在二维中，我们一般用“从 a 到 b 逆时针为正”。如果你发现自己输出的凸包是顺时针的，把 cross 的结果判断反过来即可。

2. 极角排序时忽略了共线的情况
   当两个点相对于基准点的角度完全一样时（即三点共线），如果不按距离排序，会导致凸包出现重复点或顺序错误。代码中已经用 dist2 处理了：距离近的先排。注意：在凸包算法中，通常我们希望保留离基准点最远的那个点（因为近的点会被包在里面），但这里为了排序稳定和后续扫描正确，我们让近的先排（其实不影响，因为后面扫描会淘汰掉中间的）。不过更稳妥的做法是让远的先排，这样近的会被自动弹出。如果你想修改，只需把 dist2(p0, p1) < dist2(p0, p2) 改成 >。

3. 扫描时判断条件写成 cross <= 0 还是 cross < 0？
   如果使用 cross <= 0，则会把共线的中间点也弹出，只保留端点（这是正确的，因为凸包顶点不应包含边上的内部点）。如果使用 cross < 0，则会保留共线上的所有点，可能会得到多余的点。所以在大多数竞赛中都使用 <= 0。

4. 基准点选错
   如果基准点选成了最上最右或者其他点，排序和扫描会乱套。一定要确保选的是 最下最左（y最小，y相同时x最小）。这样所有点都位于基准点的上方或右方，排序时角度从 0° 到 180° 之间，能保证逆时针顺序。

5. 只有一个点或两个点
   如果点总数少于 3 个，那么凸包就是这些点本身。我们的代码中 hull 初始压入两个点，如果只有两个点，循环不会执行，输出就是这两个点，没问题。

学了凸包之后，可以继续学什么？

• Andrew 算法：另一种更简洁的凸包算法，按 x 排序后分上下链构建，比 Graham 扫描更快。
• 计算几何基础：向量、点积、叉积、线段相交、多边形面积等，这些都是游戏开发、机器人路径规划、地理信息系统（GIS）中的基础技能。
• 凸包的应用：比如求最远点对（旋转卡壳）、求最小包围矩形、碰撞检测等。

如果你喜欢画图，还可以试试用 C++ 加上图形库（如 EasyX）把凸包画出来，看着更直观！

总结：Graham 扫描法就像排队做操一样——先找个基准，其他按角度站好，然后逐个检查左转右转，最后留下的人就是凸包。记得叉积别搞反，共线点处理好，你的程序就能轻松围出最省材料的“栅栏”。