旋转卡壳：用“卡尺法”找凸包上的最远点对

你有没有想过，一个多边形上哪两个点离得最远？比如你有一块不规则的饼干，想找到最长的切口；或者你有一张画满点的纸，想知道哪两个点相距最远。如果一个个比较所有点对，点数一多（比如10000个），就要算上亿次，太慢了。旋转卡壳就是一种又快又聪明的办法，它像一把可以旋转的卡尺，贴着多边形转一圈，就能找到最远的点对，而且只需要 O(n) 的时间（n 是凸包上的点数）。

什么是旋转卡壳？它为什么像“卡尺”？

想象你有一块木板，形状是一个凸多边形（比如一个不规则的盾牌）。你用两把平行的尺子从两边夹住它，就像用卡尺测量它的宽度。一开始，你把一把尺子贴着多边形的一条边，另一把尺子碰到的那个点就是离这条边最远的点（因为尺子平行，距离就是这条边到对点的垂直距离）。然后，你旋转尺子，让尺子贴着下一条边，同时移动另一把尺子，始终让两把尺子夹住多边形。这样转一圈，你记录下每次两把尺子碰到的点之间的距离，其中最大的那个就是最远点对的距离。

旋转卡壳的核心就是：当凸包上的边依次旋转时，它对应的最远点也会单调地向前移动，不会来回跳。所以我们可以用一个指针 j 随着边 i 的旋转而前进，就像卡尺的移动一样。

旋转卡壳的关键概念

1. 凸包上的边和对应的最远点

对于凸多边形的一条边，离这条边最远的点一定是凸包的顶点之一（因为凸包是凸的）。我们可以用三角形面积来比较：三角形面积等于叉积的绝对值的一半。对于边 (i, ni) 和顶点 j，面积 = |cross( hull[ni] - hull[i], hull[j] - hull[i] )|。面积越大，点离边越远。

旋转卡壳算法中，我们关注的不是面积值，而是面积的变化趋势。当我们从边 i 换到边 i+1 时，最远点位置只会向前（或保持不变），不会后退。所以我们可以用一个 while 循环，不断检查下一个点 (j+1)%n 是否比当前 j 离新边更远（即叉积 > 0），是的话就推进 j。

2. 为什么只用叉积的正负判断？

代码中使用了 (hull[ni] - hull[i]).cross(hull[(j+1)%n] - hull[j]) > 0。这里 cross 是叉积，它的几何意义是：向量 a 与向量 b 的叉积 a × b 的正负表示 b 在 a 的左边还是右边。对凸包而言，当我们旋转边时，最远点 j 移动的方向是顺时针（或逆时针），用叉积的正负判断下一个点是否更远：如果 (边向量) × (当前点指向下一点的向量) > 0，说明下一个点离新边的距离更大，于是更新 j。

3. 为什么只检查两个距离？

在 for 循环中，对于每条边 (i, ni)，我们只计算 ans = max(ans, (hull[i] - hull[j]).dist2()) 和 ans = max(ans, (hull[ni] - hull[j]).dist2())，也就是边两个端点到当前 j 点的距离平方。为什么不是 j 到所有点的距离？因为旋转卡壳保证，对于当前边，最远点 j 就是离该边最远的点，而该边的两个端点之间，最大距离必然来自于一个端点和 j 点（或者另一个端点和 j 点）。这听起来有点神奇，但数学上是正确的——因为凸包上最远点对一定是由某条边和它的对顶点组成的。

生活中的例子：测饼干的最长长度

假设你有一块凸多边形形状的饼干（比如一个五边形）。你想知道最远的两个点之间的距离，以便决定是否放进一个圆形的饼干盒。你可以用一把直尺和一把三角尺模拟旋转卡壳：

1. 把直尺贴着一条边，三角尺平行于直尺，移动直到碰到饼干上的点，这个点就是当前边的最远点。用笔在直尺和三角尺接触到饼干的位置做记号（比如直尺边的左端点和右端点分别到最远点）。
2. 然后旋转直尺到下一条边，同时移动三角尺（只往前推，不往后退），再次记录。
3. 一圈转完，找出所有记号中距离最大的两个点。

这样，你只需要转一圈，不用每个点都去量，省时省力。

代码实现详解

下面是一个完整的 C++ 程序，包含凸包计算（Andrew 算法）和旋转卡壳求最远点对。每行变量定义都加了中文注释。

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

struct Point {
    int x, y;
    // 向量减法
    Point operator-(const Point &o) const {
        return {x - o.x, y - o.y};
    }
    // 叉积
    int cross(const Point &o) const {
        return x * o.y - y * o.x;
    }
    // 点积
    int dot(const Point &o) const {
        return x * o.x + y * o.y;
    }
    // 距离的平方
    int dist2() const {
        return x * x + y * y;
    }
};

// 比较函数，用于排序
bool cmp(const Point &a, const Point &b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

// Andrew 算法求凸包，返回逆时针顺序的顶点
vector<Point> convexHull(vector<Point> &pts) {
    int n = pts.size();
    if (n <= 1) return pts;
    sort(pts.begin(), pts.end(), cmp); // 按 x, y 排序
    vector<Point> hull(2 * n);
    int k = 0;
    // 构造下凸包
    for (int i = 0; i < n; i++) {
        while (k >= 2 && (hull[k-1] - hull[k-2]).cross(pts[i] - hull[k-1]) <= 0)
            k--;
        hull[k++] = pts[i];
    }
    // 构造上凸包
    int t = k + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (k >= t && (hull[k-1] - hull[k-2]).cross(pts[i] - hull[k-1]) <= 0)
            k--;
        hull[k++] = pts[i];
    }
    hull.resize(k - 1);
    return hull;
}

int rotatingCalipers(vector<Point> &hull) {
    int n = hull.size();
    if (n <= 2) {
        return n == 2 ? (hull[0] - hull[1]).dist2() : 0; // 只有两个点或一个点
    }
    int j = 1;      // 当前对边最远点的索引
    int ans = 0;    // 最大距离的平方
    for (int i = 0; i < n; i++) {
        int ni = (i + 1) % n; // 下一条边
        // 当面积增加时，移动 j
        while ((hull[ni] - hull[i]).cross(hull[(j + 1) % n] - hull[j]) > 0) {
            j = (j + 1) % n;
        }
        // 更新答案：边两个端点到当前 j 点的距离
        ans = max(ans, (hull[i] - hull[j]).dist2());
        ans = max(ans, (hull[ni] - hull[j]).dist2());
    }
    return ans;
}

int main() {
    // 输入一些点（可以改成从键盘读入）
    vector<Point> points = {{0,0},{2,0},{1,2},{3,1},{0,1}};
    vector<Point> hull = convexHull(points); // 计算凸包
    // 输出凸包上的点（可选）
    cout << "凸包顶点：" << endl;
    for (auto &p : hull) {
        cout << "(" << p.x << "," << p.y << ") ";
    }
    cout << endl;
    // 旋转卡壳求最远点对距离平方
    int maxDist2 = rotatingCalipers(hull);
    cout << "最远距离的平方是：" << maxDist2 << endl;
    // 如果需要实际距离，可开平方
    // double maxDist = sqrt(maxDist2);
    // cout << "最远距离是：" << maxDist << endl;
    return 0;
}

运行说明

• 输入的点集可以是任意平面点，程序会自动求出凸包。
• 以上示例点集 {{0,0},{2,0},{1,2},{3,1},{0,1}}，凸包为 {{0,0},{3,0},{2,2},{0,1}}（按逆时针），最远点对距离平方为 10（例如 (0,0) 和 (3,1) 距离平方 10）。
• 如果你想测试其他点，修改 points 向量即可。

注意

• convexHull 函数要求输入的点至少有两个，否则返回原集合。
• rotatingCalipers 中，当凸包点数 ≤2 时，直接返回对应距离（0 或 两点距离平方）。
• 代码中 dist2() 返回距离平方，避免开方运算，加快速度。如果需要实际距离，最后用 sqrt 即可。

新手容易犯的错误

1. 凸包不是逆时针顺序：旋转卡壳要求凸包顶点按逆时针（或顺时针）顺序排列。如果凸包顺序混乱，旋转卡壳会出错。Graham 扫描和 Andrew 算法默认得到逆时针顺序，但要注意自己的实现。
2. 忘记处理 j 的移动条件：while 循环的条件是 cross(...) > 0，表示下一个点更远。如果写成 >=0 可能会漏掉平行边的情况，但通常 >0 就足够了，因为凸包上三点不共线时，等于0的情况很少见。如果需要处理共线，可以改为 >=0，但要小心死循环。
3. 只更新一个点对距离：代码中更新了 (i, j) 和 (ni, j) 两个距离，不能只更新一个。因为最远点对可能不是 i 和 j，而是 ni 和 j（比如当边旋转到接近对点时）。
4. 索引越界：旋转卡壳中 j 每次加 1 后取模 % n，但 while 循环中要保证 (j+1)%n 不会无限循环（因为距离是单调的，j 转一圈后就会停止）。通常用 while 加一个计数器防止死循环，但这里因为凸包是凸的，j 最多转一圈。
5. 整数溢出：如果坐标范围很大（比如 10^9），距离平方可能超过 int 范围。建议用 long long。代码中用了 int，适合小数据；实际竞赛中应改为 long long。

相关知识点指引

• 凸包算法：Graham 扫描、Andrew 算法。旋转卡壳依赖于凸包，必须先学会如何计算凸包。
• 叉积的应用：判断方向、计算面积、判断点在直线哪一侧。
• 最远点对的变体：求凸包的最大内接圆、最小外接矩形等，也可以用旋转卡壳。
• 最近点对：不同于最远点对，最近点对常用分治法，时间复杂度 O(n log n)。

掌握了旋转卡壳，你就能解决很多几何问题，就像拥有了一把万能卡尺！继续探索吧，加油！