旋转卡壳法 最小外接矩形

旋转卡壳法是一种计算几何的算法，用于求解平面上点集的最大直径、最远点对、最小包围圆以及最小包围矩形等问题。其中，最小包围矩形也称作最小外接矩形，是指能够包围所有点的面积最小的矩形。

在旋转卡壳法中，我们首先找到点集中的最左侧、最右侧、最上方和最下方的点，然后将它们两两配对，形成四条初始的平行于坐标轴的边界线段。接着，我们绕着其中一条边界线段，依次计算所有点到该线段的垂线距离，并记录距离最大的点。然后，我们将该点和该线段的下一个相邻线段配对，形成新的边界线段。如此重复，直到回到起点，此时就可以求得最小包围矩形。

需要注意的是，在求解最小包围矩形时，需要考虑点集的凸包。因为凸包上的点可以唯一确定最小包围矩形。如果点集不是凸包，则需要先求出凸包，然后再进行计算。

总的来说，旋转卡壳法是一种非常高效的算法，可以在O(n)的时间复杂度内解决最小包围矩形问题。

相关问题

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

以下是旋转卡壳求最小外接矩形的C++代码：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 100005;
const double eps = 1e-8;
const double pi = acos(-1.0);

struct Point {
    double x, y;
    Point() {}
    Point(double x, double y): x(x), y(y) {}
};

Point operator + (Point a, Point b) { return Point(a.x + b.x, a.y + b.y); }
Point operator - (Point a, Point b) { return Point(a.x - b.x, a.y - b.y); }
Point operator * (Point a, double p) { return Point(a.x * p, a.y * p); }
Point operator / (Point a, double p) { return Point(a.x / p, a.y / p); }

double Dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
double Cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
double Length(Point a) { return sqrt(Dot(a, a)); }
double Angle(Point a, Point b) { return acos(Dot(a, b) / Length(a) / Length(b)); }

bool cmp(Point a, Point b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

int n;
Point p[MAXN], ch[MAXN], u[MAXN], v[MAXN];

void Andrew() {
    sort(p, p + n, cmp);
    int m = 0;
    for (int i = 0; i < n; i++) {
        while (m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) < 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    for (int i = n - 2; i >= 0; i--) {
        while (m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) < 0) m--;
        ch[m++] = p[i];
    }
    if (n > 1) m--;
    ch[m] = ch[0];
}

double RotatingCalipers() {
    double ans = 1e18;
    int j = 1, k = 1, l = 1;
    for (int i = 0; i < n; i++) {
        while (fabs(Cross(ch[i + 1] - ch[i], ch[j + 1] - ch[i])) > fabs(Cross(ch[i + 1] - ch[i], ch[j] - ch[i]))) j = (j + 1) % n;
        while (fabs(Dot(ch[i + 1] - ch[i], ch[k + 1] - ch[i])) > fabs(Dot(ch[i + 1] - ch[i], ch[k] - ch[i]))) k = (k + 1) % n;
        if (i == 0) l = k;
        while (fabs(Dot(ch[i + 1] - ch[i], ch[l + 1] - ch[i])) > fabs(Dot(ch[i + 1] - ch[i], ch[l] - ch[i]))) l = (l + 1) % n;
        Point u = ch[j] - ch[i], v = ch[k] - ch[i], w = ch[l] - ch[i];
        double angle = Angle(u, v);
        double len = Length(u);
        double h = fabs(Cross(u, w)) / len;
        double w1 = len * sin(angle), w2 = sqrt(Length(v) * Length(v) - h * h);
        ans = min(ans, w1 * w2);
    }
    return ans;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    Andrew();
    double ans = RotatingCalipers();
    printf("%.2lf\n", ans);
    return 0;
}

其中 `Andrew()` 函数是求凸包的函数，`RotatingCalipers()` 函数是旋转卡壳求最小外接矩形的函数。

旋转卡壳最小外接矩形 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，以此为起点，继续以上的操作，直到找到最小的外接矩形。

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