旋转卡壳最小外接矩形 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()` 函数是旋转卡壳求最小外接矩形的函数。