题目描述

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

输入输出格式

输入格式：

 

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

50 01 01 10 10.5 0.5

输出样例#1： 

1.000

说明

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

 

 

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

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

 

所以就水出来了23333

 

#include
     
      #define ll long long#define maxn 2005using namespace std; const double eps=10e-9;inline int zt(double x){	if(fabs(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\n",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\n",ans);	return 0;}