HDU 3934

/*這是用的有旋轉卡殼的思想。
首先確定i，j，對k進行循環，知道找到第一個k使得cross(i,j,k)>cross(i,j,k+1),如果k==i進入下一次循環。
對j，k進行旋轉，每次循環之前更新最大值，然后固定一個j，同樣找到一個k使得cross(i,j,k)>cross(i,j,k+1)。對j進行++操作，繼續進行下一次，
知道j==k為止。
*/ #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>using namespace std;struct point{double x,y;
}p[1000100];
int n;int ans[1000100],st[1000100],cnt,stop;bool cmp(point A, point B){if(A.y<B.y) return true;else if(A.y==B.y){if(A.x<B.x) return true;}return false;
}double multi(point a,point b,point c){point p1; p1.x=a.x-c.x; p1.y=a.y-c.y;point p2; p2.x=b.x-c.x; p2.y=b.y-c.y;return p1.x*p2.y-p1.y*p2.x;
}void slove(){cnt=stop=0;st[stop++]=0; st[stop++]=1;for(int i=2;i<n;i++){while(stop>1&&multi(p[i],p[st[stop-1]],p[st[stop-2]])>=0) stop--;st[stop++]=i;}for(int i=0;i<stop;i++)ans[cnt++]=st[i];stop=0; st[stop++]=n-1; st[stop++]=n-2;for(int i=n-3;i>=0;i--){while(stop>1&&multi(p[i],p[st[stop-1]],p[st[stop-2]])>=0) stop--;st[stop++]=i;}for(int i=1;i<stop-1;i++)ans[cnt++]=st[i];
/*	for(int i=0;i<cnt;i++)cout<<ans[i]<<endl;cout<<endl;*/
}double Triangle(point a,point b,point c){point p1; p1.x=a.x-c.x; p1.y=a.y-c.y;point p2; p2.x=b.x-c.x; p2.y=b.y-c.y;return fabs((p1.x*p2.y-p1.y*p2.x)*1.0)/2.0;
}double Area(){int q; int j;double anst=0;for(int i=0;i<cnt;i++){j=(i+1)%cnt;q=(j+1)%cnt;while(Triangle(p[ans[i]],p[ans[j]],p[ans[q]])<=Triangle(p[ans[i]],p[ans[j]],p[ans[(q+1)%cnt]])&&q!=i)q=(q+1)%cnt;    //枚舉了當前最遠的K點 anst=max(anst,Triangle(p[ans[i]],p[ans[j]],p[ans[q]]));if(q==i) continue;while(j!=i&&q!=i){anst=max(anst,Triangle(p[ans[i]],p[ans[j]],p[ans[q]]));while(Triangle(p[ans[i]],p[ans[j]],p[ans[q]])<=Triangle(p[ans[i]],p[ans[j]],p[ans[(q+1)%cnt]])&&q!=i)q=(q+1)%cnt;j=(j+1)%cnt;}}return anst;
}int main(){while(scanf("%d",&n)!=EOF){//	if(n==-1) break;for(int i=0;i<n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);}sort(p,p+n,cmp);slove();double anst=0;anst=max(anst,Area());printf("%.2lf\n",anst);}return 0;
}