1069: [SCOI2007]最大土地面积
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define eps 1e-9
using namespace std;
struct point {
double x,y;
bool operator <(const point t) const {
return fabs(t.x-x)>eps?x<t.x:y<t.y;
}
}p[],s[];
point operator -(point t1,point t2) {
return (point){t1.x-t2.x,t1.y-t2.y};
}
double operator *(point t1,point t2) {
return t1.x*t2.y-t2.x*t1.y;
}
int n,top;
void get() {
s[]=p[];
for(int i=;i<=n;i++) {
while(top&&(s[top]-s[top-])*(p[i]-s[top])>=) top--;
s[++top]=p[i];
}
int tmp=top;
for(int i=n-;i>=;i--) {
while(top>tmp&&(s[top]-s[top-])*(p[i]-s[top])>=) top--;
s[++top]=p[i];
}
}
double cnts(point a,point b,point c) {
return fabs((b-a)*(c-a))/;
}
int main() {
double maxn=;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p+,p+n+);
get();
for(int i=;i<top;i++) {
int j=(i+)%top,k=(i+)%top,w=(j+)%top;
while(cnts(s[i],s[j],s[k])<cnts(s[i],s[j],s[k+])) k=(k+)%top;
double ans1=cnts(s[i],s[j],s[k]);
while(cnts(s[i],s[j],s[w])<cnts(s[i],s[j],s[w+])) w=(w+)%top;
double ans2=cnts(s[i],s[j],s[w]);
double ans=;
while(ans1+ans2>ans) {
ans=ans1+ans2;
j=(j+)%top;
while(cnts(s[i],s[j],s[k])<cnts(s[i],s[j],s[k+])) k=(k+)%top;
ans1=cnts(s[i],s[j],s[k]);
while(cnts(s[i],s[j],s[w])<cnts(s[i],s[j],s[w+])) w=(w+)%top;
ans2=cnts(s[i],s[j],s[w]);
}
maxn=max(maxn,ans);
}
printf("%.3lf",maxn);
}