旋转卡壳算法详解（C++实现凸包最远点对问题）

应用场景

旋转卡壳算法主要应用于以下计算几何问题：

• 求凸包上任意两点间的最大距离（即最远点对）
• 求凸包内最大面积三角形
• 求最小面积/周长外接矩形

前置知识：凸包

要使用旋转卡壳，首先需要得到点集的凸包。凸包可以理解为包裹所有点的最小凸多边形。我们可以使用 Andrew 算法或 Graham 扫描法来构建凸包。本文使用 Andrew 算法（基于排序和单调链）。

C++ 实现步骤

我们将分三步实现：
1. 定义点结构和向量运算
2. 构建凸包
3. 应用旋转卡壳求最远点对

第1步：定义点和辅助函数

#include <iostream>#include <vector>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;struct Point {    ll x, y;    Point() {}    Point(ll x, ll y) : x(x), y(y) {}        bool operator < (const Point &other) const {        return x < other.x || (x == other.x && y < other.y);    }        Point operator - (const Point &other) const {        return Point(x - other.x, y - other.y);    }};// 叉积：判断转向ll cross(const Point &a, const Point &b) {    return a.x * b.y - a.y * b.x;}// 向量长度的平方（避免开方，提高效率）ll dist2(const Point &a, const Point &b) {    ll dx = a.x - b.x;    ll dy = a.y - b.y;    return dx * dx + dy * dy;}

第2步：构建凸包（Andrew 算法）

vector<Point> convex_hull(vector<Point> pts) {    int n = pts.size();    if (n <= 1) return pts;        sort(pts.begin(), pts.end());    vector<Point> hull;    hull.reserve(n + 1);        // 下凸壳    for (int i = 0; i < n; ++i) {        while (hull.size() >= 2) {            Point a = hull[hull.size() - 2];            Point b = hull.back();            Point c = pts[i];            if (cross(b - a, c - a) <= 0) {                hull.pop_back();            } else break;        }        hull.push_back(pts[i]);    }        // 上凸壳    int lower_len = hull.size();    for (int i = n - 2; i >= 0; --i) {        while ((int)hull.size() > lower_len) {            Point a = hull[hull.size() - 2];            Point b = hull.back();            Point c = pts[i];            if (cross(b - a, c - a) <= 0) {                hull.pop_back();            } else break;        }        hull.push_back(pts[i]);    }        // 移除重复起点    if (hull.size() > 1) hull.pop_back();    return hull;}

第3步：旋转卡壳求最远点对

ll rotating_calipers(const vector<Point> &hull) {    int n = hull.size();    if (n == 1) return 0;    if (n == 2) return dist2(hull[0], hull[1]);        ll max_dist2 = 0;    int j = 1; // 对踵点指针        for (int i = 0; i < n; ++i) {        // 找到离边 hull[i] -> hull[i+1] 最远的点        // 利用叉积比较高度（面积）        while (cross(hull[(i + 1) % n] - hull[i],                     hull[(j + 1) % n] - hull[i])                > cross(hull[(i + 1) % n] - hull[i],                        hull[j] - hull[i])) {            j = (j + 1) % n;        }                // 更新最远距离（检查两个端点）        max_dist2 = max(max_dist2, dist2(hull[i], hull[j]));        max_dist2 = max(max_dist2, dist2(hull[(i + 1) % n], hull[j]));    }        return max_dist2;}

完整主函数示例

int main() {    int n;    cin >> n;    vector<Point> points(n);    for (int i = 0; i < n; ++i) {        cin >> points[i].x >> points[i].y;    }        vector<Point> hull = convex_hull(points);    ll max_d2 = rotating_calipers(hull);        cout << "最远点对距离的平方为: " << max_d2 << endl;    // 如果需要实际距离，可输出 sqrt(max_d2)    return 0;}

算法复杂度分析

- 凸包构建：O(n log n)（主要耗时在排序）
- 旋转卡壳过程：O(n)（每个点最多被访问一次）
因此整体时间复杂度为 O(n log n)，远优于暴力 O(n²) 方法。

总结

通过本教程，你已经掌握了如何用 C++ 实现旋转卡壳算法来高效求解最远点对问题。这项技术是计算几何中的重要工具，也是竞赛和面试中的高频考点。记住：先求C++凸包，再用双指针旋转卡壳，就能轻松搞定这类问题！

动手试试吧！修改输入点集，观察输出结果，加深理解。