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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
旋转卡壳~
好棒的算法啊！
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;
}