首先可以发现，矩形的一条边一定在凸包上。于是只需要旋转着枚举这条边，同时维护矩形另外三条边夹住的点。可以发现这三个点的移动都是单调的，于是复杂度 O(n) 。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const double eps=1e-8,oo=1e16; const int maxn=50010; int cmp(double x) { if (x>eps) return 1; if (fabs(x)<=eps) return 0; return -1; } struct Vector { double x,y; void rd() { scanf("%lf%lf",&x,&y); } void prt() { printf("%.5f %.5f\n",x,y); } bool operator < (const Vector &v) const { int tem=cmp(x-v.x); if (tem) return tem==-1; return cmp(y-v.y)==-1; } Vector operator + (const Vector &v) const { return (Vector){x+v.x,y+v.y}; } Vector operator - (const Vector &v) const { return (Vector){x-v.x,y-v.y}; } Vector operator * (const double &k) const { return (Vector){x*k,y*k}; } }a[maxn],f[maxn],res[4],now[4],v1,v2; typedef Vector Point; double dot(Vector v,Vector u) { return v.x*u.x+v.y*u.y; } double cross(Vector v,Vector u) { return v.x*u.y-v.y*u.x; } Vector normal(Vector v) { return (Vector){v.y,-v.x}; } double len(Vector v) { return sqrt(dot(v,v)); } int cmpy(int x,int y) { int tem=cmp(res[x].y-res[y].y); if (tem) return tem==-1; return cmp(res[x].x-res[y].x)==-1; } struct Line { Point p; Vector v; Point get(double k) { return p+v*k; } }; Point intersection(Line l1,Line l2) { Vector w=l1.p-l2.p; return l1.get(cross(l2.v,w)/cross(l1.v,l2.v)); } double ans=oo; int n,m; int main() { int mm,u; scanf("%d",&n); for (int i=1;i<=n;i++) a[i].rd(); sort(a+1,a+n+1); f[0]=a[1]; m=1; for (int i=2;i<=n;i++) { while (m>1&&cmp(cross(f[m-1]-f[m-2],a[i]-f[m-2]))>=0) m--; f[m++]=a[i]; } mm=m; for (int i=n-1;i;i--) { while (m>mm&&cmp(cross(f[m-1]-f[m-2],a[i]-f[m-2]))>=0) m--; f[m++]=a[i]; } m--; for (int i=0,j=1,x=1,y=-1;i<m;i++) { while (cmp(cross(f[i+1]-f[i],f[(j+1)%m]-f[j]))<=0) j=(j+1)%m; while (cmp(dot(f[i+1]-f[i],f[(x+1)%m]-f[x]))>=0) x=(x+1)%m; if (y==-1) y=j; while (cmp(dot(f[i+1]-f[i],f[(y+1)%m]-f[y]))<=0) y=(y+1)%m; v1=f[i+1]-f[i]; v2=normal(v1); now[0]=intersection((Line){f[j],v1},(Line){f[x],v2}); now[1]=intersection((Line){f[i],v1},(Line){f[x],v2}); now[2]=intersection((Line){f[i],v1},(Line){f[y],v2}); now[3]=intersection((Line){f[j],v1},(Line){f[y],v2}); if (cmp(len(now[0]-now[1])*len(now[1]-now[2])-ans)==-1) { ans=len(now[0]-now[1])*len(now[1]-now[2]); for (int k=0;k<4;k++) res[k]=now[k]; } } printf("%.5f\n",ans); u=0; for (int i=1;i<4;i++) u=min(u,i,cmpy); for (int i=u,cnt=0;cnt<=3;i=(i+1)%4,cnt++) res[i].prt(); }