最大内接矩形 c++

最大内接矩形问题可以使用二分答案和计算几何的方法解决，以下是 C++ 代码实现：

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

const double eps = 1e-8;

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

typedef Point Vector;

Vector operator + (Vector A, Vector B) {
    return Vector(A.x + B.x, A.y + B.y);
}

Vector operator - (Point A, Point B) {
    return Vector(A.x - B.x, A.y - B.y);
}

Vector operator * (Vector A, double p) {
    return Vector(A.x * p, A.y * p);
}

bool operator < (const Point& a, const Point& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

double Dot(Vector A, Vector B) {
    return A.x * B.x + A.y * B.y;
}

double Cross(Vector A, Vector B) {
    return A.x * B.y - A.y * B.x;
}

double Area2(Point A, Point B, Point C) {
    return Cross(B - A, C - A);
}

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

int ConvexHull(Point* p, int n, Point* ch) {
    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--;
    return m;
}

double getArea(Point* p, int n) {
    double area = 0;
    for (int i = 1; i < n - 1; i++)
        area += Cross(p[i] - p[0], p[i + 1] - p[0]);
    return area / 2;
}

double getLength(Point A, Point B) {
    return sqrt(Dot(A - B, A - B));
}

double getDist(Point A, Point B, Point C) {
    double area = fabs(Cross(B - A, C - A));
    double d = getLength(B, C);
    return area / d;
}

Point getIntersection(Point P, Vector v, Point Q, Vector w) {
    Vector u = P - Q;
    double t = Cross(w, u) / Cross(v, w);
    return P + v * t;
}

Point getCenter(Point A, Point B, Point C) {
    Vector v1 = B - A, v2 = C - A;
    double area = Cross(v1, v2);
    Vector u1 = Vector(v1.x / 2, v1.y / 2);
    Vector u2 = Vector(v2.x / 2, v2.y / 2);
    Point P = A + u1;
    Point Q = A + u2;
    return getIntersection(P, u1, Q, u2);
}

bool check(Point* p, int n, double len) {
    Point ch[100];
    int m = ConvexHull(p, n, ch);
    for (int i = 0; i < m; i++) {
        int j = (i + 1) % m;
        if (getLength(ch[j], ch[i]) <= len + eps) {
            Point C = Point((ch[i].x + ch[j].x) / 2, (ch[i].y + ch[j].y) / 2);
            double r = getDist(ch[i], ch[j], C);
            bool flag = true;
            for (int k = 0; k < n; k++) {
                if (getDist(ch[i], ch[j], p[k]) > r + eps) {
                    flag = false;
                    break;
                }
            }
            if (flag) return true;
        }
    }
    return false;
}

double solve(Point* p, int n) {
    double l = 0, r = 10000;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(p, n, mid)) r = mid;
        else l = mid;
    }
    return l;
}

int main() {
    Point p[100];
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        double x, y;
        scanf("%lf%lf", &x, &y);
        p[i] = Point(x, y);
    }
    printf("%.2lf\n", solve(p, n));
    return 0;
}

其中 `check` 函数用于判断是否存在满足条件的矩形，`solve` 函数用二分法求解最大内接矩形的边长。