bzoj1069

题意：

给你n个点，要求4个点

他们组成的面积最大

题解：

计算几何早已忘光

凸包卡壳

旋转

代码：

#include<bits/stdc++.h>
typedef long long ll;  
const int N=2005;  
using namespace std;  
int n,top;  
double ans;  
struct data{double x,y;}p[N],s[N];  
double dcmp(double a)  
{  
    if (fabs(a)<=1e-8) return 0;  
    else return a>0?1:-1;  
}  
double dis(data a,data b)  
{  
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);  
}  
data operator -(data a,data b)  
{  
    return (data){a.x-b.x,a.y-b.y};  
}  
double operator *(data a,data b)  
{  
    return a.x*b.y-a.y*b.x;  
}  
int operator <(data a,data b)  
{  
    int t=dcmp((p[1]-a)*(p[1]-b));  
    if (t==0) return dis(p[1],a)<dis(p[1],b);  
    else return t>0;  
}   
int main()  
{  
    scanf("%d",&n);  
    for (int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);  
    int t=1;  
    for (int i=2;i<=n;i++)
     if (p[i].y<p[t].y||(p[i].y==p[t].y&&p[i].x<p[t].x)) t=i;  
    swap(p[t],p[1]);  
    sort(p+2,p+n+1);  
    s[++top]=p[1];s[++top]=p[2];  
       for (int i=3;i<=n;i++)  
     {  
        while (top>1&&dcmp((p[i]-s[top-1])*(s[top]-s[top-1]))>=0) top--;  
        s[++top]=p[i];  
     }   
    s[top+1]=s[1];  
    for (int x=1;x<=top-1;x++)  
     {  
        int a=x%top+1,b=(x+2)%top+1;  
        for (int y=x+2;y<=top;y++)  
         {  
            while (a%top+1!=y&&dcmp((s[a+1]-s[x])*(s[y]-s[x])
            -(s[a]-s[x])*(s[y]-s[x]))>0) a=a%top+1;  
            while (b%top+1!=x&&dcmp((s[y]-s[x])*(s[b+1]-s[x])
            -(s[y]-s[x])*(s[b]-s[x]))>0) b=b%top+1;  
            ans=max(ans,(s[a]-s[x])*(s[y]-s[x])+(s[y]-s[x])*(s[b]-s[x]));  
         }   
     }  
    printf("%.3lf
",ans/2.0);  
    return 0;  
}