题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1069
发现 n 可以 n^2 。所以枚举对角线，分开的两部分三角形就可以旋转卡壳了。
注意坐标是实数。忘了改生成函数调了 2h+ ……
也不知道用不用管凸包上只有 3 个点的情况。反正这样的话就是枚举一个凹进去的三角形的最小面积罢了。
#include<cstdio> #include<cstring> #include<algorithm> #define db double using namespace std; const int N=2005; const db INF=4e10+5; int n,tot,sta[N],top;db ans; struct Node{ db x,y; Node(db a=0,db b=0):x(a),y(b) {}///////db!!!!!! bool operator< (const Node &b)const {return x<b.x||(x==b.x&&y<b.y);} Node operator- (const Node &b)const {return Node(x-b.x,y-b.y);} }t[N],a[N]; db Mx(db a,db b){return a>b?a:b;} db Mn(db a,db b){return a<b?a:b;} db cross(Node u,Node v){return u.x*v.y-u.y*v.x;} void get_hl() { sort(t+1,t+tot+1); for(int i=1;i<=tot;i++) { while(top>1&&cross(t[sta[top]]-t[i],t[sta[top-1]]-t[i])>=0) top--; sta[++top]=i; } for(int i=tot-1,lm=top;i;i--) { while(top>lm&&cross(t[sta[top]]-t[i],t[sta[top-1]]-t[i])>=0) top--; sta[++top]=i; } n=top-1; for(int i=1;i<=n;i++)a[i]=t[sta[i]]; } void upd(int &x){if(x>n)x-=n;if(x<=0)x+=n;} void rtc(int st) { int p0=st+1,p1=st+3;upd(p1); a[n+1]=a[1];// for(int cr=st+2;cr<=n;cr++)//<=n is ok not !=(st-1) { Node d=a[cr]-a[st]; while(cross(a[p0+1]-a[st],d)>cross(a[p0]-a[st],d))p0++,upd(p0); while(cross(d,a[p1+1]-a[st])>cross(d,a[p1]-a[st]))p1++,upd(p1); ans=Mx(ans,cross(a[p0]-a[st],d)+cross(d,a[p1]-a[st])); } } int main() { scanf("%d",&tot); for(int i=1;i<=tot;i++)scanf("%lf%lf",&t[i].x,&t[i].y); get_hl(); if(n>=4) { for(int i=1,j=n-2;i<=j;i++)rtc(i);//<=n-2 is ok printf("%.3f ",ans/2); } else { ans=INF;bool flag=0; for(int i=1;i<=n;i++) { flag=0; for(int j=1;j<=3;j++) if(t[i].x==a[j].x&&t[i].y==a[j].y) {flag=1;break;} if(flag)continue; ans=Mn(ans,cross(t[i]-a[1],t[i]-a[2])); ans=Mn(ans,cross(t[i]-a[2],t[i]-a[3])); ans=Mn(ans,cross(t[i]-a[3],t[i]-a[1])); } printf("%.3f ",(cross(a[2]-a[1],a[3]-a[1])-ans)/2); } return 0; }