头部背景图片
Decaku 's Blog |
Decaku 's Blog |

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**************************************************************
Problem: 1069
User: Decaku
Language: C++
Result: Accepted
Time:152 ms
Memory:1356 kb
****************************************************************/

#include<bits/stdc++.h>
using namespace std;
int n,top;
struct P
{
double x,y;
} p[2005],s[2005];

double dis(P a,P b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

P operator -(P a,P b)
{
P t;
t.x=a.x-b.x;
t.y=a.y-b.y;
return t;
}

double operator *(P a,P b)
{
return a.x*b.y-a.y*b.x;
}

bool operator <(P a,P b)
{
double t=(a-p[1])*(b-p[1]);
if(t==0)
return dis(a,p[1])<dis(b,p[1]);
return t<0;
}

void graham()
{
int k=1;
for(int i=2; i<=n; i++)
if(p[k].y>p[i].y||(p[k].y==p[i].y&&p[k].x>p[i].x))
k=i;
swap(p[1],p[k]);
sort(p+2,p+n+1);
s[++top]=p[1];
s[++top]=p[2];
for(int i=3; i<=n; i++)
{
while(top>1&&(p[i]-s[top-1])*(s[top]-s[top-1])<=0)
top--;
s[++top]=p[i];
}
s[top+1]=p[1];
}

double RC()
{
double ans=0;
int a,b;
for(int x=1; x<=top; x++)
{
a=x%top+1;
b=(x+2)%top+1;
for(int y=x+2; y<=top; y++)
{
while(a%top+1!=y&&(s[y]-s[x])*(s[a+1]-s[x])>(s[y]-s[x])*(s[a]-s[x]))
a=a%top+1;

while(b%top+1!=x&&(s[b+1]-s[x])*(s[y]-s[x])>(s[b]-s[x])*(s[y]-s[x]))
b=b%top+1;

ans=max((s[y]-s[x])*(s[a]-s[x])+(s[b]-s[x])*(s[y]-s[x]),ans);
}
}
return ans/2;
}

int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%lf %lf",&p[i].x,&p[i].y);
graham();
printf("%.3lf\n",RC());
}
avatar Decaku 如果人生的路有很长,愿你的荣耀永不退场。