1069: [SCOI2007]最大土地面积
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 3669 Solved: 1451
[Submit][Status][Discuss]
Description
在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成
的多边形面积最大。
Input
第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。
Output
最大的多边形面积，答案精确到小数点后3位。
Sample Input
5
0 0
1 0
1 1
0 1
0.5 0.5
0 0
1 0
1 1
0 1
0.5 0.5
Sample Output
1.000
HINT
数据范围 n<=2000, |x|,|y|<=100000
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #define eps 1e-9 8 using namespace std; 9 struct point { 10 double x,y; 11 bool operator <(const point t) const { 12 return fabs(t.x-x)>eps?x<t.x:y<t.y; 13 } 14 }p[2500],s[2500]; 15 point operator -(point t1,point t2) { 16 return (point){t1.x-t2.x,t1.y-t2.y}; 17 } 18 double operator *(point t1,point t2) { 19 return t1.x*t2.y-t2.x*t1.y; 20 } 21 int n,top; 22 void get() { 23 s[0]=p[1]; 24 for(int i=2;i<=n;i++) { 25 while(top&&(s[top]-s[top-1])*(p[i]-s[top])>=0) top--; 26 s[++top]=p[i]; 27 } 28 int tmp=top; 29 for(int i=n-1;i>=1;i--) { 30 while(top>tmp&&(s[top]-s[top-1])*(p[i]-s[top])>=0) top--; 31 s[++top]=p[i]; 32 } 33 } 34 double cnts(point a,point b,point c) { 35 return fabs((b-a)*(c-a))/2; 36 } 37 int main() { 38 double maxn=0; 39 scanf("%d",&n); 40 for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); 41 sort(p+1,p+n+1); 42 get(); 43 for(int i=0;i<top;i++) { 44 int j=(i+2)%top,k=(i+1)%top,w=(j+1)%top; 45 while(cnts(s[i],s[j],s[k])<cnts(s[i],s[j],s[k+1])) k=(k+1)%top; 46 double ans1=cnts(s[i],s[j],s[k]); 47 while(cnts(s[i],s[j],s[w])<cnts(s[i],s[j],s[w+1])) w=(w+1)%top; 48 double ans2=cnts(s[i],s[j],s[w]); 49 double ans=0; 50 while(ans1+ans2>ans) { 51 ans=ans1+ans2; 52 j=(j+1)%top; 53 while(cnts(s[i],s[j],s[k])<cnts(s[i],s[j],s[k+1])) k=(k+1)%top; 54 ans1=cnts(s[i],s[j],s[k]); 55 while(cnts(s[i],s[j],s[w])<cnts(s[i],s[j],s[w+1])) w=(w+1)%top; 56 ans2=cnts(s[i],s[j],s[w]); 57 } 58 maxn=max(maxn,ans); 59 } 60 printf("%.3lf",maxn); 61 }