Description

　　在某塊平面土地上有N個點，你可以選擇其中的任意四個點，將這片土地圍起來，當然，你希望這四個點圍成的多邊形面積最大。

Input

　　第1行一個正整數N，接下來N行，每行2個數x,y，表示該點的橫坐標和縱坐標。

Output

　　最大的多邊形面積，答案精確到小數點后3位。

Sample Input

Sample Output

HINT

數據范圍 n<=2000, |x|,|y|<=100000

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

旋轉卡殼~

好棒的算法??！

n<=2000，所以枚舉對角線，然后分別在兩邊求出最大面積三角型，更新答案即可，其中枚舉對角線ij后，在兩邊分別取兩個點，while循環尋找最大面積的頂點，因為這個頂點的面積具有單調性，所以在j循環中不用每次新設xy，這里用到了旋轉卡殼，復雜度不高~

（給的樣例真是水，我原來那份到處是錯的代碼都能過樣例……）

有幾個注意點：

1.都是double型；

2.叉積小心先后順序；

3.xy是先取模后+1，否則會超出范圍；

4.事實證明，數組開大一點是好習慣。

#include<cstdio>#include<iostream>#include<algorithm>using namespace std;int n,tot;struct node{	double x,y;}a[2005],c[2005];double dis(node u,node v){	return (u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y);}node Operator -(node u,node v){	node p;	p.x=u.x-v.x;p.y=u.y-v.y;	return p;}double operator *(node u,node v){	return u.x*v.y-u.y*v.x;}bool operator <(node u,node v){	double k=(u-a[1])*(v-a[1]);	if(k==0) return dis(u,a[1])<dis(v,a[1]);	return k<0;}void chan(){	int min=1;	for(int i=2;i<=n;i++)	  if(a[min].y>a[i].y || (a[min].y==a[i].y && a[min].x>a[i].x)) min=i;	swap(a[min],a[1]);	sort(a+2,a+n+1);	c[++tot]=a[1];c[++tot]=a[2];	for(int i=3;i<=n;i++)	{		while(tot>1 && (a[i]-c[tot-1])*(c[tot]-c[tot-1])<=0) tot--;		c[++tot]=a[i];	}}double cal(){	double ans=0;c[tot+1]=c[1];	for(int i=1;i<=tot-2;i++)	{		int x=i%tot+1,y=(i+2)%tot+1;		for(int j=i+2;j<=tot;j++)		{			while(x%tot+1!=j && (c[j]-c[i])*(c[x+1]-c[i])>(c[j]-c[i])*(c[x]-c[i])) x=x%tot+1;			while(y%tot+1!=i && (c[y+1]-c[i])*(c[j]-c[i])>(c[y]-c[i])*(c[j]-c[i])) y=y%tot+1;			ans=max(ans,(c[j]-c[i])*(c[x]-c[i])+(c[y]-c[i])*(c[j]-c[i]));		}	}	return ans;}int main(){	scanf("%d",&n);	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);	chan();	PRintf("%.3lf/n",cal()/2);	return 0;}