【分析】
打计算几何真的可以哭出来。。。
跟那个求线段最远点差不多，这题弄三个东西转一转，一个表示左端最远点，一个表示右端最远点，一个表示上面最远点。
左右两边的最远点用点积判断，上方最远点用差积判断。
【向量是最好的解决平面几何问题的，不要画图！！！哭！！！
输出那里，用的是向量加减法，乘一个比例系数，然后还用到了垂直单位向量。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 50010 const double eps=0.0000001;
const double INF=; struct P
{
double x,y;
}a[Maxn],t[Maxn];
int len,n; P operator - (P x,P y)
{
P tt;
tt.x=x.x-y.x;
tt.y=x.y-y.y;
return tt;
} P operator * (P x,double y)
{
P tt;
tt.x=x.x*y;
tt.y=x.y*y;
return tt;
} P operator + (P x,P y)
{
P tt;
tt.x=x.x+y.x;
tt.y=x.y+y.y;
return tt;
} double myabs(double x) {return x>?x:-x;} int fbs(double x)
{
if(myabs(x)<=eps) return ;
return x<?-:;
} double Dot(P x,P y) {return x.x*y.x+x.y*y.y;}
double Cross(P x,P y) {return x.x*y.y-x.y*y.x;}
bool cmp(P x,P y) {return fbs(x.x-y.x)==?(x.y<y.y):(x.x<y.x);} void chull()
{
sort(a+,a++n,cmp);
len=;
for(int i=;i<=n;i++)
{
while(len>&&Cross(t[len]-t[len-],a[i]-t[len])<=) len--;
t[++len]=a[i];
}
int k=len;
for(int i=n-;i>=;i--)
{
while(len>k&&Cross(t[len]-t[len-],a[i]-t[len])<=) len--;
t[++len]=a[i];
}len--;
t[]=t[len];
} void output()
{
for(int i=;i<len;i++)
{
printf("%lf %lf\n",t[i].x,t[i].y);
}printf("\n");
} double ans;
P op[]; void RC()
{
double L,R,H,D;
ans=INF;
int l=,r=,h=;
for(int i=;i<len;i++)
{
int j=(i+)%len;
// l=i;r=j;h=j;
// printf("%lf %lf\n",(t[h+1]-t[i]).x,(t[h+1]-t[i]).y);
// printf("%lf %lf\n",(t[h+1]-t[j]).x,(t[h+1]-t[j]).y);
while(Cross(t[h]-t[i],t[h]-t[j])<=Cross(t[h+]-t[i],t[h+]-t[j])) h=(h+)%len;
while(Dot(t[i]-t[j],t[r]-t[j])>=Dot(t[i]-t[j],t[r+]-t[j])) r=(r+)%len;
if(i==) l=r; // printf("%lf %lf\n",Dot(t[j]-t[i],t[l]-t[i]),Dot(t[j]-t[i],t[l+1]-t[i]));
while(Dot(t[j]-t[i],t[l]-t[i])>=Dot(t[j]-t[i],t[l+]-t[i])) l=(l+)%len; D=sqrt(Dot(t[i]-t[j],t[i]-t[j]));
H=Cross(t[h]-t[i],t[h]-t[j])/D;
L=-Dot(t[j]-t[i],t[l]-t[i])/D;
R=-Dot(t[i]-t[j],t[r]-t[j])/D; // printf("**%lf %lf %lf %lf\n",D,H,L,R); double now=(R+L+D)*H;
// printf("%lf %lf %d %d %d %lf\n",t[i].x,t[i].y,l,r,h,now);
if(now<ans)
{
ans=now;
op[]=t[i]-(t[j]-t[i])*(L/D);
op[]=t[j]-(t[i]-t[j])*(R/D);
P tt;
tt.x=(t[i]-t[j]).y;tt.y=-(t[i]-t[j]).x;
op[]=op[]+tt*(H/D);
op[]=op[]+tt*(H/D);
// op[0]=t[i];op[1]=t[j];op[2]=t[r];op[3]=t[l];
}
}
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
}
chull();
// output();
RC();
int fr=;
for(int i=;i<;i++) if(op[i].y<op[fr].y||fbs(op[fr].y-op[i].y)==&&op[i].x<op[i].x) fr=i;
printf("%.5lf\n",ans);
for(int i=;i<;i++)
{
if(fbs(op[i].x)==) op[i].x=;
if(fbs(op[i].y)==) op[i].y=;
}
// for(int i=0;i<4;i++) op[i].x=myabs(op[i].x),op[i].y=myabs(op[i].y);
for(int i=;i<;i++)
{
printf("%.5lf %.5lf\n",op[(fr+i)%].x,op[(fr+i)%].y);
}
return ;
}
调试过程不删了，心酸。。
2016-12-15 16:55:18