求出凸包后，矩形的一条边一定与凸包的某条边重合。

枚举每条边，求出离它最远的点和离它最左最右的点，因为那三个点是单调变化的，所以复杂度为$O(n)$。

注意精度。

 

#include
     
      #include
      
       #include
       
        #define N 50010using namespace std;typedef double D;struct P{D x,y;P(){}P(D _x,D _y){x=_x,y=_y;}}p[N],pp[N],hull[N],pivot,A,B,C,rect[8];int n,i,j,l,r,k;D w,h,ans=1e20,tmp,len;bool del[N];inline int zero(D x){return fabs(x)<1e-4;}inline int sig(D x){if(fabs(x)<1e-8)return 0;return x>0?1:-1;}inline D cross(P A,P B,P C){return(B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);}inline D distsqr(P A,P B){return(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}inline bool cmp(P a,P b){  D t=cross(pivot,a,b);  return sig(t)==1||sig(t)==0&&sig(distsqr(pivot,a)-distsqr(pivot,b))==-1;}inline void convexhull(int n,P stck[],int&m){  int i,k,top;  for(i=0;i
        
         =0)--top;    stck[++top]=pp[i];  }  m=top+1;}inline D area(P A,P B,P C){return fabs(cross(A,B,C));}inline P vertical(P A,P B){return P(A.x-B.y+A.y,A.y+B.x-A.x);}int main(){  scanf("%d",&n);  for(i=0;i
         
          -1)r=(r+1)%n;    len=sqrt(distsqr(A,B));    h=area(A,B,hull[j])/len;    w=(cross(A,C,hull[l])-cross(A,C,hull[r]))/len;    if(sig(h*w-ans)==-1){      ans=h*w;      tmp=area(A,B,hull[l])/len/len;      rect[0]=P(hull[l].x+tmp*(A.x-C.x),hull[l].y+tmp*(A.y-C.y));      tmp=h/len;      rect[3]=P(rect[0].x+tmp*(C.x-A.x),rect[0].y+tmp*(C.y-A.y));      tmp=w/len;      rect[1]=P(rect[0].x+tmp*(B.x-A.x),rect[0].y+tmp*(B.y-A.y));      rect[2]=P(rect[3].x+tmp*(B.x-A.x),rect[3].y+tmp*(B.y-A.y));    }  }  for(i=0;i<4;i++)rect[i+4]=rect[i];  for(j=0,i=1;i<4;i++)if(sig(rect[i].y-rect[j].y)==-1||sig(rect[i].y-rect[j].y)==0&&sig(rect[i].x-rect[j].x)==-1)j=i;  printf("%.0f.00000\n",ans);  for(i=0;i<4;i++)printf("%.0f.00000 %.0f.00000\n",rect[j+i].x,rect[j+i].y);  return 0;}