C++写一个求不规则多边形最大内接矩形

求不规则多边形最大内接矩形的算法有很多种，这里介绍一种基于旋转卡壳的算法。

首先，我们需要找到多边形的凸包。可以使用 Graham 扫描算法或者 Jarvis 步进算法来求解凸包。

接着，我们需要找到凸包上的两个点，使得它们与内接矩形的一条对角线重合。假设这两个点分别为 $p_1$ 和 $p_2$。

然后，我们需要利用旋转卡壳的方法求解内接矩形的另外两个顶点。具体来说，我们可以将凸包上的所有点按照极角排序，并依次考虑相邻两个点的连线。我们用一个向量 $v$ 表示两个相邻点的连线方向，并且初始时 $v$ 的长度为凸包的直径，即 $v = p_2 - p_1$。接着，我们将 $v$ 沿着凸包上的所有点逆时针旋转，直到它与凸包上的一条边重合。这时，我们就找到了内接矩形的另外两个顶点，它们与 $p_1$ 和 $p_2$ 分别构成一条对角线。

最后，我们可以计算出内接矩形的面积和位置。

下面是 C++ 的代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 二维向量
struct Vector2D {
    double x, y;
    Vector2D() {}
    Vector2D(double x, double y) : x(x), y(y) {}

    // 向量减法
    Vector2D operator- (const Vector2D& other) const {
        return Vector2D(x - other.x, y - other.y);
    }

    // 向量点积
    double dot(const Vector2D& other) const {
        return x * other.x + y * other.y;
    }

    // 向量叉积
    double cross(const Vector2D& other) const {
        return x * other.y - y * other.x;
    }

    // 向量长度的平方
    double len2() const {
        return x * x + y * y;
    }

    // 向量长度
    double len() const {
        return sqrt(x * x + y * y);
    }

    // 向量旋转
    Vector2D rotate(double angle) const {
        double c = cos(angle), s = sin(angle);
        return Vector2D(x * c - y * s, x * s + y * c);
    }
};

// 多边形顶点
struct Point {
    Vector2D pos;
    bool is_convex_hull_point;  // 是否为凸包上的点

    bool operator< (const Point& other) const {
        return pos.x < other.pos.x || (pos.x == other.pos.x && pos.y < other.pos.y);
    }
};

// 求凸包
vector<Point> convex_hull(vector<Point>& points) {
    int n = points.size();
    vector<Point> hull;
    if (n <= 1) {
        return hull;
    }

    sort(points.begin(), points.end());
    hull.resize(n * 2);
    int k = 0;

    // 求下凸壳
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && (hull[k - 1].pos - hull[k - 2].pos).cross(points[i].pos - hull[k - 2].pos) <= 0) {
            --k;
        }
        hull[k++] = points[i];
    }

    // 求上凸壳
    for (int i = n - 2, t = k + 1; i >= 0; --i) {
        while (k >= t && (hull[k - 1].pos - hull[k - 2].pos).cross(points[i].pos - hull[k - 2].pos) <= 0) {
            --k;
        }
        hull[k++] = points[i];
    }

    hull.resize(k - 1);
    for (auto& p : hull) {
        p.is_convex_hull_point = true;
    }

    return hull;
}

// 求不规则多边形的最大内接矩形
double max_inner_rectangle(const vector<Point>& hull) {
    int n = hull.size();
    double max_area = 0.0;

    // 找到凸包上的两个点，使得它们与内接矩形的一条对角线重合
    int a = 0, b = 1;
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        if (hull[j].pos.y - hull[i].pos.y > 1e-8) {
            double k = (hull[j].pos.x - hull[i].pos.x) / (hull[j].pos.y - hull[i].pos.y);
            double b1 = hull[i].pos.y - k * hull[i].pos.x;
            double b2 = hull[j].pos.y - k * hull[j].pos.x;
            double x = (b2 - b1) / k;
            Vector2D p(x, k * x + b1);
            if ((p - hull[i].pos).len2() > 1e-8 && (p - hull[j].pos).len2() > 1e-8) {
                a = i;
                b = j;
                break;
            }
        }
    }

    // 旋转卡壳求解内接矩形
    Vector2D v = hull[b].pos - hull[a].pos;
    double max_dist = v.len();
    for (int i = 0, j = 1; i < n; ++i) {
        while ((hull[(i + 1) % n].pos - hull[i].pos).cross(hull[(j + 1) % n].pos - hull[i].pos) > (hull[(i + 1) % n].pos - hull[i].pos).cross(hull[j].pos - hull[i].pos)) {
            j = (j + 1) % n;
        }
        double d = max((hull[i].pos - hull[j].pos).dot(v) / max_dist, (hull[(i + 1) % n].pos - hull[j].pos).dot(v.rotate(M_PI / 2)) / max_dist);
        max_area = max(max_area, d * max_dist);
    }

    return max_area;
}

int main() {
    vector<Point> points = {{Vector2D(0, 0), false}, {Vector2D(1, 1), false}, {Vector2D(1, 0), false}, {Vector2D(2, 1), false}, {Vector2D(3, 0), false}, {Vector2D(4, 2), false}, {Vector2D(3, 3), false}, {Vector2D(2, 3), false}, {Vector2D(1, 2), false}};
    vector<Point> hull = convex_hull(points);
    double max_area = max_inner_rectangle(hull);
    cout << "Max inner rectangle area: " << max_area << endl;
    return 0;
}