yicongli

LG4196

Mar 1st, 2019
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.98 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 db eps=1e-8;
  17. const int N=505;
  18.  
  19. inline db sqr(db x){
  20.     return x*x;
  21. }
  22.  
  23. inline int dcmp(const db &x){
  24.     if(fabs(x)<eps)return 0;
  25.     return x>0?1:-1;
  26. }
  27.  
  28. struct Point{
  29.     db x,y;
  30.    
  31.     inline Point(){}
  32.     inline Point(db _x,db _y):x(_x),y(_y){}
  33.    
  34. };
  35.  
  36. #define Vec Point
  37.  
  38. inline Vec operator +(const Vec &a,const Vec &b){
  39.     return Vec(a.x+b.x,a.y+b.y);
  40. }
  41.  
  42. inline Vec operator -(const Vec &a,const Vec &b){
  43.     return Vec(a.x-b.x,a.y-b.y);
  44. }
  45.  
  46. inline void operator +=(Vec &a,const Vec &b){
  47.     a.x+=b.x,a.y+=b.y;
  48. }
  49.  
  50. inline void operator -=(Vec &a,const Vec &b){
  51.     a.x-=b.x,a.y-=b.y;
  52. }
  53.  
  54. inline Vec operator *(const Vec &a,const db &b){
  55.     return Vec(a.x*b,a.y*b);
  56. }
  57.  
  58. inline Vec operator /(const Vec &a,const db &b){
  59.     return Vec(a.x/b,a.y/b);
  60. }
  61.  
  62. inline db Cross(const Vec &a,const Vec &b){
  63.     return a.x*b.y-a.y*b.x;
  64. }
  65.  
  66. inline db Angle(const Vec &a){
  67.     return atan2(a.y,a.x);
  68. }
  69.  
  70. struct Line{
  71.     Point S,T;
  72.     db theta;
  73.    
  74.     inline Line(){}
  75.     inline Line(const Point &A,const Point &B):S(A),T(B),theta(Angle(B-A)){}
  76. };
  77.  
  78. inline bool OnRight(const Line &a,const Point &A){
  79.     return dcmp(Cross(a.T-a.S,A-a.S))==-1;
  80. }
  81.  
  82. inline bool operator <(const Line &a,const Line &b){
  83.     if(dcmp(a.theta-b.theta))return dcmp(a.theta-b.theta)==-1;
  84.     return dcmp(Cross(a.T-a.S,b.S-a.S))==-1;
  85. }
  86.  
  87. inline Point LineCross(const Line &a,const Line &b){
  88.     Vec u=a.T-a.S;
  89.     Vec v=b.T-b.S;
  90.     Vec w=a.S-b.S;
  91.     db t=Cross(w,v)/Cross(v,u);
  92.     return a.S+u*t;
  93. }
  94.  
  95. Line Q1[N];
  96. Point Q2[N];
  97.  
  98. inline int Half(Line *A,int n,Point *B){
  99.     sort(A+1,A+n+1);
  100.     int head=0,tail=0;
  101.     Q1[0]=A[1];
  102.     for(int i=2;i<=n;++i){
  103.         while(head<tail&&OnRight(A[i],Q2[tail-1]))--tail;
  104.         while(head<tail&&OnRight(A[i],Q2[head]))++head;
  105.         Q1[++tail]=A[i];
  106.         Q2[tail-1]=LineCross(A[i],Q1[tail-1]);
  107.     }
  108.     while(head<tail&&OnRight(Q1[head],Q2[tail-1]))--tail;
  109.     while(head<tail&&OnRight(Q1[head],Q2[head]))++head;
  110.     Q2[tail]=LineCross(Q1[head],Q1[tail]);
  111.     n=0;
  112.     for(int i=head;i<=tail;++i)B[++n]=Q2[i];
  113.     return n;
  114. }
  115.  
  116. inline db Area(Point *A,int n){
  117.     db sum=Cross(A[n],A[1]);
  118.     for(int i=1;i<n;++i){
  119.         sum+=Cross(A[i],A[i+1]);
  120.     }
  121.     return sum/2;
  122. }
  123.  
  124. Point A[N];
  125. Line B[N];
  126.  
  127. int main(){
  128. //  freopen(".in","r",stdin);
  129. //  freopen(".out","w",stdout);
  130.     int n,tot=0;r(n);
  131.     while(n--){
  132.         int m;r(m);
  133.         for(int i=1;i<=m;++i){
  134.             int x,y;r(x),r(y);
  135.             A[i]=Point(x,y);
  136.         }
  137.         for(int i=1;i<m;++i){
  138.             B[++tot]=Line(A[i],A[i+1]);
  139.         }
  140.         B[++tot]=Line(A[m],A[1]);
  141.     }
  142.     n=Half(B,tot,A);
  143.     printf("%.3lf",Area(A,n));
  144.     return 0;
  145. }
Add Comment
Please, Sign In to add comment