[BZOJ1069][SCOI2007]最大土地面积(水平扫描法求凸包+旋转卡壳)

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

先求凸包，再枚举对角线，随着对角线的斜率上升，另外两个点的在凸包上的位置也是单调的。

水平扫描法：先将所有点按x排序，然后从左往右边扫边求出上凸壳，然后从右往左扫出下凸壳。最后会发现a[tot]=a[1]。

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=;

 int n,r,p1,p2,q[N];

 double ans;

 struct P{

     double x,y;

     bool operator <(const P &b)const{ return x==b.x ? y<b.y : x<b.x; }

     P operator -(const P &b)const{ return (P){x-b.x,y-b.y}; }

     double operator *(const P &b)const{ return x*b.y-y*b.x; }

 }a[N];

 double cj(int x,int y,int z){ return (a[x]-a[y])*(a[z]-a[y]); }

 int main(){

     freopen("bzoj1069.in","r",stdin);

     freopen("bzoj1069.out","w",stdout);

     scanf("%d",&n);

     rep(i,,n) scanf("%lf%lf",&a[i].x,&a[i].y);

     sort(a+,a+n+);

     rep(i,,n){

         while (r> && cj(q[r],q[r-],i)>=) r--;

         q[++r]=i;

     }

     int rr=r;

     for (int i=n-; i>=; i--){

         while (r>rr && cj(q[r],q[r-],i)>=) r--;

         q[++r]=i;

     }

     rep(i,,r-){

         int p1=i+,p2=i+;

         rep(j,i+,r-){

             while (p1<j- && cj(q[j],q[i],q[p1])<=cj(q[j],q[i],q[p1+])) p1++;

             while (p2<=j || (p2<r- && cj(q[p2],q[i],q[j])<=cj(q[p2+],q[i],q[j]))) p2++;

             ans=max(ans,cj(q[j],q[i],q[p1])+cj(q[p2],q[i],q[j]));

         }

     }

     printf("%.3lf\n",ans/);

     return ;

 }