G53 旋转卡壳【计算几何】

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
struct Point
{
    double x,y;
    Point(){}
    Point(double a,double b):x(a),y(b){}
    void input(){scanf("%lf%lf",&x,&y);} 
    friend bool operator<(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
    friend Point operator-(Point a,Point b){ return {a.x-b.x,a.y-b.y};}
    friend double det(Point a,Point b){return a.x*b.y-a.y*b.x;}
    friend double dis(Point a,Point b){Point p=a-b;return sqrt(p.x*p.x+p.y*p.y);}
}P[N],sta[N];int n,top;

void Andrew()
{
    sort(P+1,P+n+1);
	top=0;
    for(int i=1;i<=n;i++)
    {
        while( top>1 && det(sta[top]-sta[top-1],P[i]-sta[top-1])<=0 ) top--;
        sta[++top]=P[i];
    }
    int t=top;
    for(int i=n-1;i>=1;i--)
    {
        while( top>t && det(sta[top]-sta[top-1],P[i]-sta[top-1])<=0 ) top--;
        sta[++top]=P[i];
    }
	n=top-1;  
}
double rotating_calipers() //旋转卡壳
{
    double res=0;
    for(int i=1; i<=n-2; i++)
    {
        for(int j=i+2,a=i+1,b=j+1;j<=n-1;j++)
        {
            while(det(sta[i]-sta[j],sta[a]-sta[j])<det(sta[i]-sta[j],sta[a+1]-sta[j]))a=a%n+1;
            while(det(sta[j]-sta[i],sta[ b ]-sta[i])<det(sta[j]-sta[i],sta[b+1]-sta[i]))b=b%n+1;
            res=max(res,det(sta[i]-sta[j],sta[a]-sta[j])+det(sta[j]-sta[i],sta[ b ]-sta[i]));
        }
    }
    return res/2.0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)P[i].input();
    Andrew();
    printf("%.3lf\n",rotating_calipers());
    return 0;
}