「BZOJ1069」[SCOI2007]最大土地面积

Description

在某块平面土地上有NN个点,你可以选择其中的任意四个点,将这片土地围起来,当然,你希望这四个点围成
的多边形面积最大

Input

11行一个正整数NN,接下来NN行,每行22个数x,yx,y,表示该点的横坐标和纵坐标。

Output

最大的多边形面积,答案精确到小数点后33位。

Sample Input

1
2
3
4
5
6
5
0 0
1 0
1 1
0 1
0.5 0.5

Sample Output

1
1.000

HINT

数据范围 n2000,x,y<=100000n\leq 2000, |x|,|y|<=100000

Solution

旋转卡壳的模板题。 单峰的性质,一图胜过千语。

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}


const int N = 3000*2;
struct Pt {
double x, y;
Pt(){}
Pt(double _x, double _y) {x = _x, y = _y;}
double d() {
return x * x + y * y;
}
}a[N];
typedef Pt Vec;
Vec operator + (const Vec a, const Vec b) {
return Vec(a.x + b.x, a.y + b.y);
}
Vec operator - (const Vec a, const Vec b) {
return Vec(a.x - b.x, a.y - b.y);
}
double cross(const Vec a, const Vec b) {
return a.x * b.y- b.x* a.y;
}
#define eps 1e-8
int E(double x) {
if(x < -eps) return -1;
if(x > eps) return 1;
return 0;
}
int n;
bool cmp(Vec x, Vec y) {
Vec t1 = x - a[1];
Vec t2 = y - a[1];
double v = cross(t1, t2);
if(E(v)) return v > 0;
else return x.d() < y.d();
}
int st[N], top;
double area(Vec x, Vec y, Vec z) {
Vec t1 = x - z;
Vec t2 = y - z;
double v = cross(t1, t2);
return fabs(v) / 2;
}
int main() {
n = read();
int p = 0;
a[0].x = a[0].y = 1e9;
for(int i = 1; i <= n; ++i) {
scanf("%lf%lf",&a[i].x,&a[i].y);
if(a[i].x < a[p].x) p =i;
else if(a[i].x == a[p].x && a[i].y < a[p].y) p = i;
}
swap(a[p], a[1]);
sort(a + 2 , a + 1 + n, cmp);
/* for(int i = 1; i <= n; ++i) {
printf("%d:(%lf,%lf)\n", i,a[i].x, a[i].y);
}*/
st[++top] = 1;
for(int i = 2; i <= n; ++i) {
while(top > 1 && cross(a[st[top]] - a[st[top - 1]], a[i] - a[st[top - 1]]) <= 0) --top;
st[++top] = i;
}
// for(int i = 1; i <= top; ++i) {
// printf("%d:(%lf,%lf)\n", i,a[st[i]].x, a[st[i]].y);
// }
/* double ans = 0;
for(int i = 1; i <= top; ++i) {
for(int j = 1; j <= top; ++j) {
for(int k = 1; k <= top; ++k) {
for(int l = 1; l <= top; ++l) {
Vec t1 = a[st[j]] - a[st[i]];
Vec t2 = a[st[l]] - a[st[i]];
double res = 0;
res += cross(t1, t2) / 2;
t1 = a[st[k]] - a[st[l]];
t2 = a[st[k]] - a[st[j]];
res += cross(t1, t2) / 2;
ans = max(ans, res);
}
}
}
}*/
/* double ans = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
for(int k = 1; k <= n; ++k) {
for(int l = 1; l <= n; ++l) {
Vec t1 = a[j] - a[i];
Vec t2 = a[l] - a[i];
double res = 0;
res += cross(t1, t2) / 2;
t1 = a[k] - a[l];
t2 = a[k] - a[j];
res += cross(t1, t2) / 2;
ans = max(ans, res);
}
}
}
}*/
for(int i = 1; i <= top; ++i)
st[top + i] = st[i];
double ans = 0;
for(int i = 1; i <= top; ++i) {
int k1 = i + 1;
int k2 = i + 3;
int x = st[i];
for(int j = i + 2; j < top * 2; ++j) {
int y = st[j];
while(k2 < top + i && area(a[x], a[y], a[st[k2 + 1]]) >= area(a[x], a[y], a[st[k2]])) ++k2;
while(k1 < j && area(a[x], a[y], a[st[k1 + 1]]) >= area(a[x], a[y], a[st[k1]])) ++k1;
ans = max(ans, area(a[x], a[y], a[st[k2]]) + area(a[x], a[y], a[st[k1]]));
}
}
printf("%.3lf\n", ans);
return 0;
}