[SCOI2007]最大土地面积

题目描述

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

输入输出格式

输入格式：

第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。

输出格式：

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

输入输出样例

输入样例#1： 

5
0 0
1 0
1 1
0 1
0.5 0.5

输出样例#1： 

1.000

说明

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

2000的话因为可以N^2，所以我们先处理出凸包(最优的四个顶点肯定在凸包上，可以考虑反证法)，然后枚举一下对角线，我们的目的是要让两侧的

三角形面积最大。随着枚举的节点的极角的增大，剩下两个点的移动也是单调的，因为三角形面积的函数在凸包上是单增的。

所以就水出来了23333

#include<bits/stdc++.h>
#define ll long long
#define maxn 2005
using namespace std; 
const double eps=10e-9;

inline int zt(double x){
	if(fabs(x)<eps) return 0;
	return x>0?1:-1;
}

struct node{
	double x,y;
	
	node operator -(const node &U)const{
		return (node){x-U.x,y-U.y}; 
	}
	node operator +(const node &U)const{
		return (node){x+U.x,y+U.y};
	}
	
	bool operator <(const node &U)const{
		return zt(x-U.x)?zt(x-U.x)<0:zt(y-U.y)<0;
	}
}a[maxn],hill[maxn];
int n,m,p[maxn];
double ans;

inline double Xmul(node x,node y){
	return x.x*y.y-x.y*y.x;
}

inline bool equal(node x,node y){
	return (!zt(x.x-y.x)&&!zt(x.y-y.y));
}

inline void get_hill(){
	sort(a+1,a+n+1);
	int tot=0,now=0;
	
	for(int i=1;i<=n;i++){
		while(now>=2&&zt(Xmul(a[i]-a[p[now]],a[p[now]]-a[p[now-1]]))>=0) now--;
		p[++now]=i;
	}
	for(int i=1;i<=now;i++) hill[i]=a[p[i]];
	tot=now,now=0;

	for(int i=1;i<=n;i++){
		while(now>=2&&zt(Xmul(a[i]-a[p[now]],a[p[now]]-a[p[now-1]]))<=0) now--;
		p[++now]=i;
	}
	for(int i=now;i;i--) if(!equal(a[p[i]],hill[tot])) hill[++tot]=a[p[i]];
	if(equal(hill[tot],hill[1])) tot--;
	
//	for(int i=1;i<=tot;i++) printf("%lf %lf
",hill[i].x,hill[i].y);
	
	n=tot;	
}

inline int mo(int x,const int ha){
	if(x>=ha) return x-ha;
	else return x;
}

inline void solve(){
	for(int i=1;i<=n;i++){
		int pt1=i+1,pt2=i+3;
		for(int j=i+2;j<=n;j++){
			int topt=mo(pt1,n)+1;
			while(Xmul(hill[topt]-hill[i],hill[j]-hill[i])>Xmul(hill[pt1]-hill[i],hill[j]-hill[i])){
				pt1=topt;
				topt=mo(pt1,n)+1;
			}
			
			topt=mo(pt2,n)+1;
			while(Xmul(hill[j]-hill[i],hill[topt]-hill[i])>Xmul(hill[j]-hill[i],hill[pt2]-hill[i])){
				pt2=topt;
				topt=mo(pt2,n)+1;
			}			
			
			ans=max(ans,(Xmul(hill[pt1]-hill[i],hill[j]-hill[i])+Xmul(hill[j]-hill[i],hill[pt2]-hill[i]))/2.00);
		}
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
	get_hill();
	solve();
	
	printf("%.3lf
",ans);
	return 0;
}