【POJ】1389 Area of Simple Polygons

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #define MAXN 100010
  5 struct Line
  6 {
  7     int left,right,high,flag;
  8 };
  9 struct node
 10 {
 11     int sum,cover;
 12 };
 13 Line p[MAXN];
 14 node tree[MAXN<<2];
 15 int x[MAXN];
 16 inline bool Out(int x1,int y1,int x2,int y2)
 17 {
 18     return x1==-1&&y1==-1&&x2==-1&&y2==-1;
 19 }
 20 int cmp1(const void *a,const void *b)
 21 {
 22     return *(int *)a-*(int *)b;
 23 }
 24 int cmp2(const void *a,const void *b)
 25 {
 26     return (*(Line *)a).high-(*(Line *)b).high;
 27 }
 28 int Bin(int val,int low,int high)
 29 {
 30     int mid;
 31     while(low<high)
 32     {
 33         mid=(low+high)>>1;
 34         if(x[mid]==val)
 35             return mid;
 36         if(x[mid]<val)
 37             low=mid+1;
 38         else
 39             high=mid;
 40     }
 41 }
 42 void Build(int L,int R,int rt)
 43 {
 44     tree[rt].cover=tree[rt].sum=0;
 45     if(L!=R)
 46     {
 47         int mid=(L+R)>>1;
 48         Build(L,mid,rt<<1);
 49         Build(mid+1,R,rt<<1|1);
 50     }
 51 }
 52 inline void PushUp(int L,int R,int rt)
 53 {
 54     if(tree[rt].cover)
 55         tree[rt].sum=x[R+1]-x[L];
 56     else if(L==R)
 57         tree[rt].sum=0;
 58     else
 59         tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
 60 }
 61 void Update(int st,int en,int flag,int L,int R,int rt)
 62 {
 63     if(st<=L&&R<=en)
 64     {
 65         tree[rt].cover+=flag;
 66         PushUp(L,R,rt);
 67     }
 68     else
 69     {
 70         int mid=(L+R)>>1;
 71         if(mid>=st)
 72             Update(st,en,flag,L,mid,rt<<1);
 73         if(en>mid)
 74             Update(st,en,flag,mid+1,R,rt<<1|1);
 75         PushUp(L,R,rt);
 76     }
 77 }
 78 int main()
 79 {
 80     int n,i,m,flag,x1,y1,x2,y2,ans,st,en;
 81     for(n=flag=0;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);)
 82     {
 83         if(Out(x1,y1,x2,y2))
 84             flag++;
 85         else
 86             flag=0;
 87         if(flag==2)
 88             break;
 89         if(flag)
 90         {
 91             qsort(x,n,sizeof(x[0]),cmp1);
 92             qsort(p,n,sizeof(p[0]),cmp2);
 93             for(i=m=0;i<n;i++)
 94             {
 95                 if(x[i]!=x[m])
 96                     x[++m]=x[i];
 97             }
 98             Build(0,m-1,1);
 99             for(i=ans=0;i<n-1;i++)
100             {
101                 st=Bin(p[i].left,0,m+1);
102                 en=Bin(p[i].right,0,m+1);
103                 Update(st,en-1,p[i].flag,0,m-1,1);
104                 ans+=(p[i+1].high-p[i].high)*tree[1].sum;
105             }
106             printf("%d\n",ans);
107             n=0;
108         }
109         else
110         {
111             x[n]=x1;
112             p[n].flag=1;
113             p[n].left=x1;
114             p[n].right=x2;
115             p[n++].high=y1;
116             x[n]=x2;
117             p[n].flag=-1;
118             p[n].left=x1;
119             p[n].right=x2;
120             p[n++].high=y2;
121         }
122     }
123     return 0;
124 }
新博客：www.zhixiangli.com