Advertisement
yicongli

LG4250

Mar 12th, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.57 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=2e5+7;
  17. const db eps=1e-10;
  18. inline int dcmp(const db &a){
  19.     if(fabs(a)<eps)return 0;
  20.     return a<0?-1:1;
  21. }
  22.  
  23. struct Point{db x,y;};
  24. #define Vec Point
  25. inline Vec operator +(const Vec &a,const Vec &b){return Vec{a.x+b.x,a.y+b.y};}
  26. inline Vec operator -(const Vec &a,const Vec &b){return Vec{a.x-b.x,a.y-b.y};}
  27. inline Vec operator *(const Vec &a,const db &b){return Vec{a.x*b,a.y*b};}
  28. inline db operator *(const Vec &a,const Vec &b){return a.x*b.y-a.y*b.x;}
  29. inline db Angle(const Vec &a){return atan2(a.y,a.x);}
  30.  
  31. struct Line{
  32.     Point S;
  33.     Vec V;
  34.     db ang;
  35.     inline Line (){}
  36.     inline Line (const Point &s,const Point &v):S(s),V(v),ang(Angle(v)){}
  37. };
  38.  
  39. inline bool operator < (const Line &a,const Line &b){
  40.     double alpha=a.ang-b.ang;
  41.     if(dcmp(alpha))return dcmp(alpha)==-1;
  42.     return dcmp(a.V*(b.S-a.S))==-1;
  43. }
  44.  
  45. inline Point cross(const Line &a,const Line &b){
  46.     Vec u=a.S-b.S;
  47.     db t=(u*b.V)/(b.V*a.V);
  48.     return a.S+a.V*t;
  49. }
  50.  
  51. inline bool OnRight(const Line &a,const Point &b){
  52.     return dcmp((b-a.S)*a.V)==1;
  53. }
  54.  
  55. int head,tail;
  56. Line Q[N];
  57.  
  58. inline int Half(Line *A,int n,Point *B){
  59.     sort(A+1,A+n+1);
  60.     Q[head=tail=0]=A[1];
  61.     for(int i=2;i<=n;++i){
  62.         if(!dcmp(A[i].ang-A[i-1].ang))continue;
  63.         while(head<tail&&OnRight(A[i],cross(Q[tail],Q[tail-1])))
  64.         --tail;
  65.         while(head<tail&&OnRight(A[i],cross(Q[head],Q[head+1])))
  66.         ++head;
  67.         Q[++tail]=A[i];
  68.     }
  69.     while(head<tail&&OnRight(Q[head],cross(Q[tail],Q[tail-1])))
  70.     --tail;
  71.     while(head<tail&&OnRight(Q[tail],cross(Q[head],Q[head+1])))
  72.     ++head;
  73.     int m=0;
  74.     for(int i=head;i<tail;++i){
  75.         B[m++]=cross(Q[i],Q[i+1]);
  76.     }
  77.     B[m++]=cross(Q[head],Q[tail]);
  78.     return m;
  79. }
  80.  
  81. Line L[N];
  82. Point P[N];
  83.  
  84. int main(){
  85. //  freopen(".in","r",stdin);
  86. //  freopen(".out","w",stdout);
  87.     int n,tot=0;r(n);
  88.     for(int i=0;i<n;++i){
  89.         r(P[i].x),r(P[i].y);
  90.     }
  91.     db sum=0;
  92.     for(int i=2;i<n;++i){
  93.         sum+=(P[i-1]-P[0])*(P[i]-P[0]);
  94.     }
  95.     P[n]=P[0];
  96.     for(int i=0;i<n;++i){
  97.         L[++tot]=Line(P[i],P[i+1]-P[i]);
  98.     }
  99.     for(int i=1;i<n;++i){
  100.         db a=P[0].y-P[1].y-P[i].y+P[i+1].y;
  101.         db b=P[1].x-P[0].x+P[i].x-P[i+1].x;
  102.         db c=P[0].x*P[1].y-P[0].y*P[1].x-P[i].x*P[i+1].y+P[i].y*P[i+1].x;
  103.         if(dcmp(b))L[++tot]=Line(Point{0,-c/b},Vec{-b,a});
  104.         else if(dcmp(a))L[++tot]=Line(Point{-c/a,0},Vec{-b,a});
  105.         else if(c>0)return puts("0.0000"),0;
  106.     }
  107.     n=Half(L,tot,P);
  108.     db ans=0;
  109.     for(int i=2;i<n;++i){
  110.         ans+=(P[i-1]-P[0])*(P[i]-P[0]);
  111.     }
  112.     printf("%.4lf",ans/sum);
  113.     return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement