最大内接四边形

发表于2020-08-17更新于2023-09-15字数统计648阅读时长6分

SCOI2007 最大土地面积

Description

选取平面上的 4 个点，使得围成的四边形的面积最大 (n≤2000n \le 2000)。

Solution

最大四边形的顶点一定在凸包上。
当凸包顶点数大于 3 时，先选取一条对角线，则其它两个点到对角线的距离具有单峰性，套旋转卡壳即可求出最大四边形面积。
当凸包顶点数等于 3 时，最大四边形面积为凸包面积减去内部点与凸包上的点构成的最小的三角形面积。
当凸包顶点数等于 2 时，面积为 0。

Code

最大内接四边形
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define PI acos(-1)

using namespace std;

constexpr int MAXN = 3e3 + 3;

struct Vec2 {
    Vec2() = default;
    Vec2(double _x, double _y) : x(_x), y(_y) {}

    friend inline bool operator<(const Vec2& a, const Vec2& b) {
        return fabs(a.x - b.x) < 1e-8 ? a.y < b.y : a.x < b.x;
    }

    friend inline Vec2 operator-(const Vec2& a, const Vec2& b) {
        return Vec2(a.x - b.x, a.y - b.y);
    }

    friend inline double operator*(const Vec2& a, const Vec2& b) {
        return a.x * b.y - a.y * b.x;  //×
    }
    double x = 0, y = 0;
} vec[MAXN], cov[MAXN];
int n, top, Up;

inline void convex() {
    top = 0, Up = 0;
    sort(vec + 1, vec + n + 1);
    for (int i = 1; i <= n; i++) {  //下凸壳
        while (top > 1 && (cov[top] - cov[top - 1]) * (vec[i] - cov[top]) < 1e-8)
            cov[top--] = Vec2(0, 0);
        cov[++top] = vec[i];
    }
    Up = top;                          //上凸壳起点
    for (int i = n - 1; i > 0; i--) {  //上凸壳
        while (top > Up && (cov[top] - cov[top - 1]) * (vec[i] - cov[top]) < 1e-8)
            cov[top--] = Vec2(0, 0);
        cov[++top] = vec[i];
    }
}

inline double calc(double res = .0) {
    if (top <= 3) return 0.0; //凸包只有2个点
    if (top == 4) ; //凸包只有3个点
    for (int i = 1; i < top; i++) {
        int up = (i + 2) % (top - 1) == 0 ? (i + 2) : (i + 2) % (top - 1);
        int down = i;
        for (int j = i + 2; j < i + top - 2; j++) {
            auto s = cov[i], t = cov[j % (top - 1) == 0 ? j : j % (top - 1)];
            while (true) {
                auto s1 = fabs((t - cov[up]) * (s - cov[up]));
                auto s2 = fabs((t - cov[up + 1]) * (s - cov[up + 1]));
                if (s1 < s2 + 1e-8) up = up % (top - 1) + 1;
                else break;
            }
            while (true) {
                auto s1 = fabs((t - cov[down]) * (s - cov[down]));
                auto s2 = fabs((t - cov[down + 1]) * (s - cov[down + 1]));
                if (s1 < s2 + 1e-8) down = down % (top - 1) + 1;
                else break;
            }
            res = max(res, fabs((cov[up]- s) * (cov[up] - t)) +
                               fabs((cov[down] - s) * (cov[down] - t)));
        }
    }
    return res / 2;
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> vec[i].x >> vec[i].y;
    convex();
    cout << setprecision(3) << fixed << calc() << endl;;
    return 0;
}