yicongli

LG3187

Mar 13th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.15 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define db double
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=50005;
  17. const db eps=1e-7;
  18.  
  19. inline int dcmp(db a){
  20.     if(fabs(a)<eps)return 0;
  21.     return a>0?1:-1;
  22. }
  23.  
  24. struct Point{
  25.     db x,y;
  26.     inline bool operator < (const Point &a){return x==a.x?y<a.y:x<a.x;}
  27. };
  28. #define Vec Point
  29. inline Vec operator + (const Point &a,const Point &b){return Point{a.x+b.x,a.y+b.y};}
  30. inline Vec operator - (const Point &a,const Point &b){return Point{a.x-b.x,a.y-b.y};}
  31. inline Vec operator * (const Point &a,const db    &b){return Point{a.x*b,a.y*b};}
  32. inline Vec operator / (const Point &a,const db    &b){return Point{a.x/b,a.y/b};}
  33. inline db  operator * (const Point &a,const Point &b){return a.x*b.y-a.y*b.x;}
  34. inline db dot(const Point &a,const Point &b){return a.x*b.x+a.y*b.y;}
  35. inline db sqr(const db &a){return a*a;}
  36. inline db norm(const Vec &a){return sqrt(sqr(a.x)+sqr(a.y));}
  37. inline bool cmp(const Vec &a,const Vec &b){
  38.     return (a*b>0)||(a*b==0&&norm(a)<norm(b));
  39. }
  40.  
  41. struct Line{Point s,v;};
  42.  
  43. inline Point Cross(const Line &a,const Line &b){
  44.     Vec w=a.s-b.s;
  45.     db t=(w*b.v)/(b.v*a.v);
  46.     return a.s+a.v*t;
  47. }  
  48.  
  49. int sta[N],top;
  50. inline int convex(Point *A,int n){
  51.     Point tmp=A[1];
  52.     for(int i=2;i<=n;++i)if(A[i]<tmp)tmp=A[i];
  53.     for(int i=1;i<=n;++i)A[i]=A[i]-tmp;
  54.     sort(A+1,A+n+1,cmp);
  55.     sta[top=1]=1;
  56.     for(int i=2;i<=n;++i){
  57.         while(top>1&&(A[sta[top]]-A[sta[top-1]])*(A[i]-A[sta[top-1]])<=0)top--;
  58.         sta[++top]=i;
  59.     }
  60.     for(int i=1;i<=top;++i)A[i]=A[sta[i]]+tmp;
  61.     return top;
  62. }
  63.  
  64. inline db area(const Point &a,const Point &b,const Point &c){
  65.     return fabs((b-a)*(c-a));
  66. }
  67.  
  68. Point P[N];
  69.  
  70. inline void print(const Point &a){
  71.     printf("%.5f %.5f\n",a.x+eps,a.y+eps);
  72. }
  73.  
  74. int main(){
  75.     //freopen(".in","r",stdin);
  76.     //freopen(".out","w",stdout);
  77.     int n;scanf("%d",&n);
  78.     for(int i=1;i<=n;++i){
  79.         scanf("%lf%lf",&P[i].x,&P[i].y);
  80.         P[i]=P[i];
  81.     }
  82.     n=convex(P,n);
  83.     int L=1,R=1,U=3;
  84.     for(int i=2;i<=n;++i){
  85.         if(dot(P[0]-P[i],P[1]-P[0])<dot(P[0]-P[L],P[1]-P[0]))L=i;
  86.     }
  87.     for(int i=2;i<=n;++i){
  88.         if(dot(P[0]-P[i],P[1]-P[0])>dot(P[0]-P[R],P[1]-P[0]))R=i;
  89.     }
  90.     int a,b,c,d;
  91.     db ans=1e60;
  92.     for(int i=1;i<=n;++i){
  93.         while(dot(P[R%n+1]-P[R],P[i%n+1]-P[i])>0)R=R%n+1;
  94.         while(dot(P[L%n+1]-P[L],P[i%n+1]-P[i])<0)L=L%n+1;
  95.         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;
  96.         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]));
  97.         if(area<ans){
  98.             ans=area,a=i,b=L,c=R,d=U;
  99.         }
  100.     }
  101.     Line line[4];
  102.     Vec V=P[a%n+1]-P[a];
  103.     Vec E=Vec{-V.y,V.x};
  104.     line[0]=Line{P[a],V};
  105.     line[1]=Line{P[c],E};
  106.     line[2]=Line{P[d],V};
  107.     line[3]=Line{P[b],E};
  108.     Point A[4];
  109.     A[0]=Cross(line[0],line[1]);
  110.     A[1]=Cross(line[1],line[2]);
  111.     A[2]=Cross(line[2],line[3]);
  112.     A[3]=Cross(line[3],line[0]);
  113.     printf("%.5f\n",ans);
  114.     int pos=0;
  115.     for(int i=1;i<4;++i){
  116.         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;
  117.     }
  118.     for(int i=0;i<4;++i){
  119.         print(A[(pos+i)&3]);
  120.     }
  121. }
  122. /*
  123. 8
  124. 9 3
  125. 13 1
  126. 1 27
  127. 3 31
  128. 27 39
  129. 31 37
  130. 37 9
  131. 39 13
  132.  
  133. */
Add Comment
Please, Sign In to add comment