解题思路
首先有一个结论是最小覆盖矩形的一条边一定是凸包上的一条边，那么就可以枚举凸包上的点，然后旋转卡壳卡出其余三个点。算坐标的时候拿向量去乘一下。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 50005;
const double eps = 1e-8;
int n,stk[MAXN],top,p[MAXN],cnt,st;
double ans=1e20;
struct Node{
double x,y;
Node(double _x=0,double _y=0) {x=_x;y=_y;}
}node[MAXN],point[5];
Node operator-(Node A,Node B){return Node(A.x-B.x,A.y-B.y);}
Node operator+(Node A,Node B){return Node(A.x+B.x,A.y+B.y);}
Node operator*(Node A,double k){return Node(A.x*k,A.y*k);}
inline double dot(Node A,Node B){return A.x*B.x+A.y*B.y;}
inline double cross(Node A,Node B){return A.x*B.y-A.y*B.x;}
inline int dcmp(double x){if(fabs(x)<=eps) return 0;return x>0?1:-1;}
inline bool cmp(Node A,Node B){return A.x==B.x?A.y<B.y:A.x<B.x;}
inline double check(int a,int b,int c){return cross(node[a]-node[b],node[c]-node[a]);}
inline double dis(Node A,Node B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
inline double calc(int a,int b,int c){return cross(node[c]-node[a],node[c]-node[b]);}
inline void rotating(){
p[cnt+1]=p[1];double Dis,L,R,H,tmp;
for(int i=1,a=2,b=2,c;i<=cnt;i++){
while(dot(node[p[a+1]]-node[p[i+1]],node[p[i]]-node[p[i+1]])
<=dot(node[p[a]]-node[p[i+1]],node[p[i]]-node[p[i+1]]))
a=(a==cnt)?1:a+1;
while(fabs(calc(p[i],p[i+1],p[b]))<=fabs(calc(p[i],p[i+1],p[b+1])))
b=(b==cnt)?1:b+1;
if(i==1) c=a;
while(dot(node[p[c+1]]-node[p[i]],node[p[i+1]]-node[p[i]])
<=dot(node[p[c]]-node[p[i]],node[p[i+1]]-node[p[i]]))
c=(c==cnt)?1:c+1;
Dis=dis(node[p[i]],node[p[i+1]]);
L=fabs(dot(node[p[c]]-node[p[i+1]],node[p[i]]-node[p[i+1]]))/Dis;
R=fabs(dot(node[p[a]]-node[p[i]],node[p[i+1]]-node[p[i]]))/Dis;
H=fabs(calc(p[i],p[i+1],p[b]))/Dis;
tmp=(L+R-Dis)*H;
if(tmp<ans){
ans=tmp;
point[1]=node[p[i+1]]-(node[p[i+1]]-node[p[i]])*(L/Dis);
point[2]=point[1]+(node[p[i+1]]-node[p[i]])*((R+L-Dis)/Dis);
point[3]=point[2]+(node[p[a]]-point[2])*(H/dis(node[p[a]],point[2]));
point[4]=point[3]+(node[p[i]]-node[p[i+1]])*((R+L-Dis)/Dis);
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&node[i].x,&node[i].y);
sort(node+1,node+1+n,cmp);
for(int i=1;i<=n;i++){
while(top>1 && dcmp(check(stk[top],stk[top-1],i))!=1) top--;
stk[++top]=i;
}top--;
for(int i=1;i<=top;i++) p[++cnt]=stk[i];top=0;
for(int i=n;i;i--){
while(top>1 && dcmp(check(stk[top],stk[top-1],i))!=1) top--;
stk[++top]=i;
}top--;
for(int i=1;i<=top;i++) p[++cnt]=stk[i];
rotating();printf("%.5lf
",ans);point[st].y=1e20;
for(int i=1;i<=4;i++){
if(fabs(point[i].x)<eps) point[i].x=0;
if(fabs(point[i].y)<eps) point[i].y=0;
}
for(int i=1;i<=4;i++)
if((point[i].y<point[st].y) || (point[i].y==point[st].y && point[i].x<point[st].x))
st=i;
printf("%.5lf %.5lf
",point[st].x,point[st].y);
for(int i=0;i<3;i++)
printf("%.5lf %.5lf
",point[(i+st)%4+1].x,point[(i+st)%4+1].y);
return 0;
}