bzoj1069 [SCOI2007] 最大土地面积

题意:在某块平面土地上有$N$($N\leq 2000$)个点,你可以选择其中的任意四个点,将这片土地围起来,当然,你希望这四个点围成的多边形面积最大。

求出凸包,旋转卡壳枚举一个对角线,确定了这条对角线的基础上再套一次旋转卡壳枚举第二个对角线,更新最大面积。复杂度$O(nlogn+n^2)$。

其中四边形面积的求法:设四个点为$i1,j1,i2,j2$,那么根据叉积可以表示有向面积易得$S=\frac{\overrightarrow{i_1 i_2}\times \overrightarrow{i_1 j_2} + \overrightarrow{j_1 i_2}\times \overrightarrow{j_1 j_2} }{2}$。也等价于两条对角线的叉积绝对值除以$2$。

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
#include <bits/stdc++.h>
using namespace std;
double eps=1e-10;
const int maxn=2000+5;
struct P {
double x,y;
P(double x=0,double y=0): x(x),y(y) {}
P operator+(P oth) {return P(x+oth.x,y+oth.y);}
P operator*(double k) {return P(x*k,y*k);}
P operator-(P oth) {return P(x-oth.x,y-oth.y);}
double dot(P oth) {return x*oth.x+y*oth.y;}
double det(P oth) {return x*oth.y-y*oth.x;}
};
P pts[maxn],hl[maxn];
int n,K;
bool cmp(P A,P B)
{
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
}
void grh()
{
K=0;
for(int i=1;i<=n;i++) {
while(K>=2 && (hl[K]-hl[K-1]).det(pts[i]-hl[K])<=0.0) K--;
hl[++K]=pts[i];
}
int up=K;
for(int i=n-1;i>=1;i--) {
while(K>up && (hl[K]-hl[K-1]).det(pts[i]-hl[K])<=0.0) K--;
hl[++K]=pts[i];
}
K--;
}
int getmod(int id,int mo)
{
if(id%mo==0) return mo;
else return id%mo;
}
double GetArea(P a,P b,P c,P d)
{
P dx1=a-c,dy1=b-c,dx2=a-d,dy2=b-d;
return abs(dx1.det(dy1))/2.0+abs(dx2.det(dy2))/2.0;
}
double rot()
{
if(K==2) {return 0.0;}
int si=1,sj=1;
for(int i=1;i<=K;i++) {
if(cmp(hl[i],hl[si])) si=i;
if(cmp(hl[sj],hl[i])) sj=i;
}
int i1=si,i2=si,j1=sj,j2=sj;double res=-1.0;
while(i1!=sj || j1!=si) {
i2=si,j2=sj;
while(i2!=sj || j2!=si) {
if(i1!=i2 && i1!=j2 && j1!=i2 && j1!=j2) {
res=max(res,GetArea(hl[i1],hl[j1],hl[i2],hl[j2]));
}
if((hl[getmod(i2+1,K)]-hl[i2]).det(hl[getmod(j2+1,K)]-hl[j2])<0) i2=getmod(i2+1,K);
else j2=getmod(j2+1,K);
}
if((hl[getmod(i1+1,K)]-hl[i1]).det(hl[getmod(j1+1,K)]-hl[j1])<0) i1=getmod(i1+1,K);
else j1=getmod(j1+1,K);
}
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&pts[i].x,&pts[i].y);
sort(pts+1,pts+1+n,cmp);
grh();
printf("%.3f\n",rot());
return 0;
}