Submit: 3177 Solved: 1255
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
Source
数学问题 计算几何 凸包 旋转卡壳
要找四个点围成最大面积，显然这四个点应该在凸包上。
所以先求出凸包来。
之后当然不能四重循环枚举选点。
可以枚举选其中的两个点，假装作辅助线把凸包分成两半，在两半中各自找一个面积最大的三角形，三角形顶点就是使得选中面积最大的点。
对于一条边而言，凸包上的点到这条边的距离是满足单峰性质的，所以可以开两个指针单调扫过去。
这似乎就是传说中的旋转卡壳？
迷之WA，（一边肝菲特狗一边）对拍半天就是找不出错。
最后静态查错试着把33行的>0改成>=0就过了
简直要气哭
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const double eps=1e-8; 9 const int mxn=3010; 10 struct Point{ 11 double x,y; 12 }a[mxn]; 13 Point operator + (Point L,Point r){return (Point){L.x+r.x,L.y+r.y};} 14 Point operator - (Point L,Point r){return (Point){L.x-r.x,L.y-r.y};} 15 inline double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;} 16 inline double dist(Point a,Point b){ 17 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 18 } 19 int n; 20 int st[mxn],top=0; 21 int Pcmp(Point x,Point y){ 22 double res=Cross(x-a[1],y-a[1]); 23 if(abs(res)<=eps)return dist(x,a[1])<dist(y,a[1]); 24 else return res>0; 25 } 26 void HAM(){ 27 int p=1,i; 28 for(i=2;i<=n;i++) 29 if(a[i].x<a[p].x || (a[i].x==a[p].x && a[i].y>a[p].y)) p=i; 30 swap(a[1],a[p]); 31 sort(a+2,a+n+1,Pcmp); 32 for(i=1;i<=n;i++){ 33 while(top>1 && Cross(a[i]-a[st[top-1]],a[st[top]]-a[st[top-1]])>=0)top--; 34 st[++top]=i; 35 } 36 return; 37 } 38 void solve(){ 39 HAM(); 40 st[top+1]=1; 41 double ans=0; 42 int hd,tl,i,j; 43 for(i=1;i<=top;i++){ 44 hd=i%top+1;tl=(i+2)%top+1; 45 for(j=i+2;j<=top;j++){ 46 Point tmp=a[st[j]]-a[st[i]]; 47 while(tl%top+1!=i && Cross(tmp,a[st[tl+1]]-a[st[i]])>Cross(tmp,a[st[tl]]-a[st[i]])) 48 tl=tl%top+1; 49 while(hd%top+1!=j && Cross(a[st[hd+1]]-a[st[i]],tmp)>Cross(a[st[hd]]-a[st[i]],tmp)) 50 hd=hd%top+1; 51 ans=max(ans,Cross(tmp,a[st[tl]]-a[st[i]])+Cross(a[st[hd]]-a[st[i]],tmp)); 52 } 53 } 54 printf("%.3lf",ans/2); 55 return; 56 } 57 int main(){ 58 // freopen("in.txt","r",stdin); 59 // freopen("out1.txt","w",stdout); 60 int i,j; 61 scanf("%d",&n); 62 for(i=1;i<=n;i++) 63 scanf("%lf%lf",&a[i].x,&a[i].y); 64 solve(); 65 return 0; 66 }