[BZOJ 1069][SCOI 2007] 最大土地面积

发表于

题目大意

平面上有 \(n\) 个点，可以选择其中的任意四个点将这片土地围起来，求这四个点围成的多边形的最大面积。

\(4 \leqslant n \leqslant 2,000\)

\(|x|, \; |y| \leqslant 100,000\)

题目链接

BZOJ 1069

题解

凸包 + 旋转卡壳。

枚举凸包上的一条对角线作为四边形的对角线，在对角线两侧各找到一个点使得两侧的三角形面积最大，可以用旋转卡壳的方法在上一次的基础上快速求得。

如果凸包是三角形，需要特殊处理一下，但数据中好像没有这样的情况。。。（但我还是写了。。。）

代码

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 <cstdio>
#include <cmath>
#include <algorithm>
const int MAXN = 2005;
const double EPS = 1e-9;
int dcmp(double x) {
    if (fabs(x) <= EPS) return 0;
    if (x > EPS) return 1;
    else return -1;
}
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    bool operator<(const Point &another) const {
        return x < another.x || (x == another.x && y < another.y);
    }
    bool operator==(const Point &another) const {
        return !dcmp(x - another.x) && !dcmp(y - another.y);
    }
    friend Point operator-(const Point &a, const Point &b) {
        return Point(a.x - b.x, a.y - b.y);
    }
    friend double cross(const Point &a, const Point &b) {
        return a.x * b.y - a.y * b.x;
    }
} P[MAXN], ch[MAXN];
int getConvexHell(int n) {
    std::sort(P, P + n);
    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 - 1; ~i; i--) {
        while (m > k && cross(ch[m - 1] - ch[m - 2], P[i] - ch[m - 2]) <= 0) m--;
        ch[m++] = P[i];
    }
    m > 1 ? m-- : 0;
    return m;
}
double rotatingCalipers(int n) {
    double ans = 0;
    for (int curr = 0; curr < n; curr++) {
        int left = (curr + 2) % n, right = (curr + 1) % n;
        for (int up = (curr + 1) % n; up < n; up++) {
            Point currV = ch[up] - ch[curr];
            while ((right + 1) % n != up && cross(ch[right + 1] - ch[curr], currV) > cross(ch[right] - ch[curr], currV))
                right = (right + 1) % n;
            while ((left + 1) % n != curr && cross(currV, ch[left + 1] - ch[curr]) > cross(currV, ch[left] - ch[curr]))
                left = (left + 1) % n;
            ans = std::max(ans, cross(ch[right] - ch[curr], currV) + cross(currV, ch[left] - ch[curr]));
        }
    }
    return ans;
}
void calcTriangle(int n) {
    static bool onConvexHell[MAXN];
    for (int i = 0; i < n; i++)
        onConvexHell[i] = (P[i] == ch[0] || P[i] == ch[1] || P[i] == ch[2]);
    double trianArea = cross(ch[1] - ch[0], ch[2] - ch[0]), ans = 0;
    for (int i = 0; i < n; i++) if (!onConvexHell[i]) {
        double temp = std::min(std::min(cross(ch[0] - P[i], ch[1] - P[i]), cross(ch[1] - P[i], ch[2] - P[i])),
                cross(ch[2] - P[i], ch[0] - P[i]));
        ans = std::max(ans, trianArea - temp);
    }
    printf("%.3lf\n", ans / 2);
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lf %lf", &P[i].x, &P[i].y);
    int m = getConvexHell(n);
    if (m == 3) calcTriangle(n);
    else printf("%.3lf\n", rotatingCalipers(m) / 2);
    return 0;
}