省选前练模板系列
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100010,inf=1e9; const double eps=1e-11; int dcmp(double a, double b) { if (a < b - eps) return -1; else if (a > b + eps) return 1; else return 0; } struct vec{ double x,y,ang; vec(){}; vec(double a,double b){x=a,y=b;} vec operator-(vec a){return vec(x-a.x,y-a.y);} vec operator+(vec a){return vec(x+a.x,y+a.y);} bool operator<(const vec&p) const { return dcmp(x,p.x)<0 || (dcmp(x,p.x)==0 && y < p.y); } }p[maxn],ch[maxn]; int n,m,pp,mi,k; double A,P; double cross(vec a,vec b){return a.x*b.y-b.x*a.y;} double dot(vec a,vec b){return a.x*b.x+a.y*b.y;} double dis(vec a,vec b){return sqrt((double)dot(a-b,a-b));} int main(){ while(scanf("%d",&n)!=EOF&&n){ m=0;A=1e15;P=1e15; for(int i=0;i<n;++i){ scanf("%lf%lf",&p[i].x,&p[i].y); } sort(p,p+n); for(int i=0;i<n;++i){ while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--; ch[m++]=p[i]; } k=m; for(int i=n-2;i>=0;--i){ while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--; ch[m++]=p[i]; } if(n>1)--m; for(int i=0;i<m;++i)cout<<ch[i].x<<' '<<ch[i].y<<endl; ch[m]=ch[0]; int t=1,l=1,r=1; for(int b=0;b<m;++b){ while(cross(ch[b+1]-ch[b],ch[t+1]-ch[t])>eps)t=(t+1)%m; while(dot(ch[b+1]-ch[b],ch[r+1]-ch[r])>eps)r=(r+1)%m; if(b==0)l=(r+1)%m; while(dot(ch[b+1]-ch[b],ch[l+1]-ch[l])<-eps)l=(l+1)%m; double d=dis(ch[b+1],ch[b]); double h=(double)cross(ch[b+1]-ch[b],ch[t]-ch[b])/d; double w=(double)(dot(ch[r]-ch[b],ch[b+1]-ch[b])-dot(ch[b+1]-ch[b],ch[l]-ch[b]))/d; A=min(A,2*(h+w));P=min(P,h*w); } printf("%.2lf %.2lf ",P,A); } return 0; } /* */