Guest User

UVA 109

a guest
Jul 20th, 2015
362
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Abinash Ghosh
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cctype>
  5. #include <cmath>
  6. #include <cstring>
  7. #include <climits>
  8. #include <iostream>
  9. #include <iomanip>
  10. #include <vector>
  11. #include <list>
  12. #include <stack>
  13. #include <queue>
  14. #include <map>
  15. #include <set>
  16. #include <string>
  17. #include <utility>
  18. #include <sstream>
  19. #include <algorithm>
  20. #include <ctime>
  21. #include <cassert>
  22. using  namespace  std;
  23.  
  24. #define PI acos(-1.0)
  25. #define mem(a,b) memset(a,b,sizeof(a))
  26. #define gcd(a,b) __gcd(a,b)
  27. #define pb push_back
  28. #define mp make_pair
  29. #define x first
  30. #define y second
  31. #define Sort(x) sort(x.begin(),x.end())
  32. #define FOR(i, b, e) for(int i = b; i <= e; i++)
  33. #define FORR(i, b, e) for(int i = b; i >= e; i--)
  34. #define FORI(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
  35. #define pr(x) cout<<x<<"\n"
  36. #define pr2(x,y) cout<<x<<" "<<y<<"\n"
  37. #define pr3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n";
  38. #define READ(f) freopen(f, "r", stdin)
  39. #define WRITE(f) freopen(f, "w", stdout)
  40.  
  41. typedef  long long ll;
  42. typedef  pair <int, int> pii;
  43. typedef  pair <double , double> pdd;
  44. typedef  pair <ll , ll > pll;
  45. typedef  vector <int> vi;
  46. typedef  vector <pii> vpii;
  47. typedef  vector <ll > vl;
  48.  
  49. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  50. //int dx[]={1,1,0,-1,-1,-1,0,1};
  51. //int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  52. //int dx[]={2,1,-1,-2,-2,-1,1,2};
  53. //int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  54.  
  55. #define MAX 100007
  56. #define eps 1e-9
  57. pii p0,pnt[100],res[50][100],power[30];
  58. int add[1000];
  59. int cross(pii o, pii a, pii b) {
  60.   return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
  61. }
  62. inline bool inConvexPolygon(int q,int nc,pii p)
  63. {
  64.     FOR(i,0,nc-1)
  65.     {
  66.         if(cross(p,res[q][i],res[q][(i+1)%(nc)])<0)return false;
  67.     }
  68.     return true;
  69. }
  70. void convexHull(int np,int &nc,int k)
  71. {
  72.     sort(pnt,pnt+np);
  73.     int j=0;
  74.     FOR(i,0,np-1)
  75.     {
  76.        while(j>=2&&cross(res[k][j-2],res[k][j-1],pnt[i])<=0)j--;
  77.           res[k][j++]=pnt[i];
  78.     }
  79.     for(int i=np-2,t=j+1;i>=0;i--)
  80.     {
  81.        while(j>=t&&cross(res[k][j-2],res[k][j-1],pnt[i])<=0)j--;
  82.           res[k][j++]=pnt[i];
  83.     }
  84.     // printf("%d\n",j-1);
  85.     nc=j-1;
  86. }
  87.  
  88. int  pArea(int nc,int q)
  89. {
  90.     int area=0,n=nc;
  91.     for(int i=0;i<n;++i)
  92.         area+= res[q][i].x * res[q][(i+1)%n].y - res[q][i].y * res[q][(i+1)%n].x;
  93.     return area;
  94. }
  95. int main()
  96. {
  97.     //READ("in.in");
  98.     //WRITE("out.out");
  99.     int k=0,n,nc[100];
  100.     while(1)
  101.     {
  102.         scanf("%d",&n);
  103.         if(n==-1)break;
  104.         k++;
  105.         FOR(i,0,n-1)
  106.             scanf("%d%d",&pnt[i].x,&pnt[i].y);
  107.  
  108.         convexHull(n,nc[k],k);
  109.         //pr(nc[k]);
  110.     }
  111.     int m=0;
  112.     int ans=0;
  113.     while(scanf("%d%d",&pnt[m].x,&pnt[m].y)!=EOF)
  114.     {
  115.         FOR(i,1,k)
  116.         {
  117.             if(add[i]==0&&inConvexPolygon(i,nc[i],pnt[m]))
  118.             {
  119.                 add[i]=1;
  120.                // pr(k);
  121.                 break;
  122.             }
  123.         }
  124.         m++;
  125.     }
  126.     FOR(i,1,k)
  127.     if(add[i])ans+=pArea(nc[i],i);
  128.     printf("%.2lf",ans/2.0);
  129.  
  130.     return 0;
  131. }
RAW Paste Data