Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define db double
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const int N=50005;
- const db eps=1e-7;
- inline int dcmp(db a){
- if(fabs(a)<eps)return 0;
- return a>0?1:-1;
- }
- struct Point{
- db x,y;
- inline bool operator < (const Point &a){return x==a.x?y<a.y:x<a.x;}
- };
- #define Vec Point
- inline Vec operator + (const Point &a,const Point &b){return Point{a.x+b.x,a.y+b.y};}
- inline Vec operator - (const Point &a,const Point &b){return Point{a.x-b.x,a.y-b.y};}
- inline Vec operator * (const Point &a,const db &b){return Point{a.x*b,a.y*b};}
- inline Vec operator / (const Point &a,const db &b){return Point{a.x/b,a.y/b};}
- inline db operator * (const Point &a,const Point &b){return a.x*b.y-a.y*b.x;}
- inline db dot(const Point &a,const Point &b){return a.x*b.x+a.y*b.y;}
- inline db sqr(const db &a){return a*a;}
- inline db norm(const Vec &a){return sqrt(sqr(a.x)+sqr(a.y));}
- inline bool cmp(const Vec &a,const Vec &b){
- return (a*b>0)||(a*b==0&&norm(a)<norm(b));
- }
- struct Line{Point s,v;};
- inline Point Cross(const Line &a,const Line &b){
- Vec w=a.s-b.s;
- db t=(w*b.v)/(b.v*a.v);
- return a.s+a.v*t;
- }
- int sta[N],top;
- inline int convex(Point *A,int n){
- Point tmp=A[1];
- for(int i=2;i<=n;++i)if(A[i]<tmp)tmp=A[i];
- for(int i=1;i<=n;++i)A[i]=A[i]-tmp;
- sort(A+1,A+n+1,cmp);
- sta[top=1]=1;
- for(int i=2;i<=n;++i){
- while(top>1&&(A[sta[top]]-A[sta[top-1]])*(A[i]-A[sta[top-1]])<=0)top--;
- sta[++top]=i;
- }
- for(int i=1;i<=top;++i)A[i]=A[sta[i]]+tmp;
- return top;
- }
- inline db area(const Point &a,const Point &b,const Point &c){
- return fabs((b-a)*(c-a));
- }
- Point P[N];
- inline void print(const Point &a){
- printf("%.5f %.5f\n",a.x+eps,a.y+eps);
- }
- int main(){
- //freopen(".in","r",stdin);
- //freopen(".out","w",stdout);
- int n;scanf("%d",&n);
- for(int i=1;i<=n;++i){
- scanf("%lf%lf",&P[i].x,&P[i].y);
- P[i]=P[i];
- }
- n=convex(P,n);
- int L=1,R=1,U=3;
- for(int i=2;i<=n;++i){
- if(dot(P[0]-P[i],P[1]-P[0])<dot(P[0]-P[L],P[1]-P[0]))L=i;
- }
- for(int i=2;i<=n;++i){
- if(dot(P[0]-P[i],P[1]-P[0])>dot(P[0]-P[R],P[1]-P[0]))R=i;
- }
- int a,b,c,d;
- db ans=1e60;
- for(int i=1;i<=n;++i){
- while(dot(P[R%n+1]-P[R],P[i%n+1]-P[i])>0)R=R%n+1;
- while(dot(P[L%n+1]-P[L],P[i%n+1]-P[i])<0)L=L%n+1;
- while((P[i%n+1]-P[i])*(P[U]-P[i])<(P[i%n+1]-P[i])*(P[U%n+1]-P[i]))U=U%n+1;
- db area=(P[i%n+1]-P[i])*(P[U]-P[i])/norm(P[i%n+1]-P[i])*(norm(P[i%n+1]-P[i])+dot(P[R]-P[i%n+1],P[i%n+1]-P[i])/norm(P[i%n+1]-P[i])+dot(P[i]-P[L],P[i%n+1]-P[i])/norm(P[i%n+1]-P[i]));
- if(area<ans){
- ans=area,a=i,b=L,c=R,d=U;
- }
- }
- Line line[4];
- Vec V=P[a%n+1]-P[a];
- Vec E=Vec{-V.y,V.x};
- line[0]=Line{P[a],V};
- line[1]=Line{P[c],E};
- line[2]=Line{P[d],V};
- line[3]=Line{P[b],E};
- Point A[4];
- A[0]=Cross(line[0],line[1]);
- A[1]=Cross(line[1],line[2]);
- A[2]=Cross(line[2],line[3]);
- A[3]=Cross(line[3],line[0]);
- printf("%.5f\n",ans);
- int pos=0;
- for(int i=1;i<4;++i){
- if(dcmp(A[i].y-A[pos].y)==-1||(dcmp(A[i].y-A[pos].y)==0&&A[i].x<A[pos].x))pos=i;
- }
- for(int i=0;i<4;++i){
- print(A[(pos+i)&3]);
- }
- }
- /*
- 8
- 9 3
- 13 1
- 1 27
- 3 31
- 27 39
- 31 37
- 37 9
- 39 13
- */
Add Comment
Please, Sign In to add comment