旋转卡壳最小外接矩形 C++代码加注释

旋转卡壳（Rotating Calipers）算法用于求解凸包的最小外接矩形（Minimum Bounding Rectangle）。下面是C++实现代码，带有注释说明：

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

const int N = 100010; // 点数的最大值

struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) : x(x), y(y) {}
    Point operator - (const Point& p) const {
        return Point(x - p.x, y - p.y);
    }
};

int n; // 输入点数
Point p[N]; // 输入点

// 计算叉积 (P1-P0)x(P2-P0)
double cross(const Point& p1, const Point& p2, const Point& p0) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

// 计算距离的平方
double dis2(const Point& A, const Point& B) {
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

// 旋转卡壳
double rotating_calipers(Point* p, int n) {
    double ans = 1e18; // 最小面积
    int j = 2; // 第二个点
    for (int i = 1; i <= n; i++) {
        // 以 p[i] 为起点，旋转卡壳
        while (cross(p[i + 1], p[j + 1], p[i]) > cross(p[i + 1], p[j], p[i])) {
            j = j % n + 1; // 旋转
        }
        ans = min(ans, dis2(p[i], p[j])); // 更新答案
    }
    return ans;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    sort(p + 1, p + n + 1, [](Point a, Point b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }); // 按 x 从小到大排序
    double ans = rotating_calipers(p, n);
    printf("%.2lf\n", sqrt(ans)); // 输出最小面积的平方根
    return 0;
}

注释中已经详细解释了每一段代码的含义，这里再简单介绍一下旋转卡壳的思路：

1. 将所有点按 x 坐标从小到大排序，取最左边的点 p1；
2. 以 p1 为起点，找到与其构成的向量中，与 y 轴平行的向量（即最上方的向量）；
3. 以这个向量的终点作为起点，继续找到与其构成的向量中，与 x 轴平行的向量（即最右边的向量）；
4. 以这个向量的终点作为起点，继续找到与其构成的向量中，与 y 轴相反的向量（即最下方的向量）；
5. 以这个向量的终点作为起点，继续找到与其构成的向量中，与 x 轴相反的向量（即最左边的向量）；
6. 回到起点 p1，以此为起点，继续以上的操作，直到找到最小的外接矩形。

其中，每次找到一个向量，可以通过计算叉积的符号来判断向量是否满足要求。