不说了，待我吐完这口老血。。。。
一开始我看题目说配spj以为就可以随便输出4个点的位置，然而....spj居然只是用来判-0.00000的，调了一下午，最后改成输出最下面的顶点然后逆时针输出就过了，喷血。。。不认真读题的后果
思路嘛，矩形一定有一条边在凸包上，枚举这条边，旋转卡壳来维护其他三个点，对面的顶点用三角形面积大小判断，而两边的点则用点积来判断就好了。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #define maxn 50021 #define F(a) (a<0 ? a=-a : 0) using namespace std; int top,n; struct P{ double x,y; P(double a=0,double b=0):x(a),y(b){} bool operator<(const P& b)const{return x==b.x?y<b.y:x<b.x;} }p[maxn],s[maxn],q[10]; typedef P vec; vec operator+(vec a,vec b){return vec(a.x+b.x,a.y+b.y);} vec operator-(P a,P b){return vec(a.x-b.x,a.y-b.y);} vec operator*(vec a,double p){return vec(a.x*p,a.y*p);} vec operator/(vec a,double p){return vec(a.x/p,a.y/p);} double cross(vec a,vec b){return a.x*b.y-a.y*b.x;} double area(P a,P b,P c){return fabs(cross(a-b,a-c));} double dot(vec a,vec b){return a.x*b.x+a.y*b.y;} double len(vec a){return sqrt(a.x*a.x+a.y*a.y);} double angle(vec a,vec b){return acos(dot(a,b)/len(a)/len(b));} bool cmp(P a,P b){return a.y==b.y ? a.x > b.x : a.y < b.y;} void make(){ sort(p+1,p+1+n); for(int i=1;i<=n;i++){ while(top>1&&cross(s[top]-s[top-1],p[i]-s[top])<=0)top--; s[++top]=p[i]; }int m=top; for(int i=n-1;i>=1;i--){ while(top>m&&cross(s[top]-s[top-1],p[i]-s[top])<=0)top--; s[++top]=p[i]; } } void solve(){ double tmp,ans=1e100; int a,b,c;s[top+1]=s[1]; a=b=c=2; for(int i=2;i<=top;i++){ while(cross(s[a+1]-s[i],s[i-1]-s[i])>=cross(s[a]-s[i],s[i-1]-s[i]))a=a%top+1; while(dot(s[b+1]-s[i],s[i-1]-s[i])<=dot(s[b]-s[i],s[i-1]-s[i]))b=b%top+1; if(i==2)c=a; while(dot(s[c+1]-s[i-1],s[i]-s[i-1])<=dot(s[c]-s[i-1],s[i]-s[i-1]))c=c%top+1; double dis=len(s[i]-s[i-1]); double L=dot(s[c]-s[i],s[i-1]-s[i])/dis;F(L); double R=dot(s[b]-s[i-1],s[i]-s[i-1])/dis;F(R); double H=area(s[i],s[i-1],s[a])/len(s[i]-s[i-1]);F(H); tmp=(L+R-dis)*H; if(tmp<ans){ ans=tmp; q[1]=s[i]-(s[i]-s[i-1])*(L/dis); q[2]=q[1]+(s[i]-s[i-1])*((R+L-dis)/dis); q[3]=q[2]+(s[b]-q[2])*(H/len(s[b]-q[2])); q[4]=q[3]+(s[i-1]-s[i])*((R+L-dis)/dis); } } printf("%.5lf\n",ans); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y); make();solve(); int st=0;q[0].y=1e9; for(int i=1;i<=4;i++)if(q[i].y<q[st].y||(q[i].y==q[st].y&&q[i].x<q[st].x))st=i; printf("%.5lf %.5lf\n",q[st].x,q[st].y); for(int i=0;i<3;i++){ printf("%.5lf %.5lf\n",q[(i+st)%4+1].x,q[(i+st)%4+1].y); } return 0; }
