旋转卡壳就是先求出凸包。然后在凸包上枚举四边形的对角线两側分别找面积最大的三角形

因为在两側找面积最大的三角形的顶点是单调的所以复杂度就是n2

单调的这个性质能够自行绘图感受一下，似乎比較显然

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<vector>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define ll long long

#define N 2002

using namespace std;

struct W{double x,y;}a[N],st[N];

int n,top;

W operator-(W a,W b)

{

    return (W){a.x-b.x,a.y-b.y};

}

double dis(W a,W b)

{

    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}

double operator*(W a,W b)

{

    return a.x*b.y-a.y*b.x;

}

bool operator<(W c,W d)

{

    double t=(c-a[1])*(d-a[1]);

    if(t==0)return dis(c,a[1])<dis(d,a[1]);

    return t<0;

}

void Graham()

{

    int k=1;

    for(int i=2;i<=n;i++)

        if(a[k].y>a[i].y||(a[k].y==a[k].y&&a[k].x>a[i].x))

            k=i;

    swap(a[k],a[1]);sort(a+1,a+n+1);

    st[++top]=a[1],st[++top]=a[2];

    for(int i=3;i<=n;i++)

    {

        while(top>1&&(a[i]-st[top-1])*(st[top]-st[top-1])<=0)top--;

        st[++top]=a[i];

    }

}

double Rotating_caliper()

{

    double mx=0;st[top+1]=a[1];

    int a,b;

    for(int x=1;x<=top;x++)

    {

        a=x%top+1,b=(x+2)%top+1;

        for(int y=x+2;y<=top;y++)

        {

            while(a%top+1!=y&&(st[y]-st[x])*(st[a+1]-st[x])>(st[y]-st[x])*(st[a]-st[x]))a=a%top+1;

            while(b%top+1!=x&&(st[b+1]-st[x])*(st[y]-st[x])>(st[b]-st[x])*(st[y]-st[x]))b=b%top+1;

            mx=max(mx,(st[y]-st[x])*(st[a]-st[x])+(st[b]-st[x])*(st[y]-st[x]));

        }

    }

    return mx;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

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

    Graham();

    printf("%.3lf",Rotating_caliper()/2);

    return 0;

}