HDU 1255 覆盖的面积(线段树面积并)

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 const int N=2005;
 8 int col[N<<2];
 9 double sum1[N<<2],sum2[N<<2],x[N<<2];
10 struct seg
11 {
12     double l,r,h;
13     int s;
14     seg(){}
15     seg(double l,double r,double h,int s):l(l),r(r),h(h),s(s){}
16     bool operator<(const seg &D){
17         return h<D.h;
18     }
19 }a[N];
20 
21 void PushUp(int rt,int l,int r)
22 {
23     if(col[rt])sum1[rt]=x[r+1]-x[l];
24     else if(l==r)sum1[rt]=0;
25     else sum1[rt]=sum1[rt<<1]+sum1[rt<<1|1];
26 
27     if(col[rt]>=2)sum2[rt]=x[r+1]-x[l];
28     else if(l==r)sum2[rt]=0;
29     else if(col[rt]==1)sum2[rt]=sum1[rt<<1]+sum1[rt<<1|1];
30     else if(col[rt]==0)sum2[rt]=sum2[rt<<1]+sum2[rt<<1|1];
31 }
32 void Update(int L,int R,int C,int l,int r,int rt)
33 {
34     if(L<=l&&r<=R)
35     {
36         col[rt]+=C;
37         PushUp(rt,l,r);
38         return;
39     }
40     int mid=(l+r)>>1;
41     if(L<=mid)Update(L,R,C,l,mid,rt<<1);
42     if(R>mid)Update(L,R,C,mid+1,r,rt<<1|1);
43     PushUp(rt,l,r);
44 }
45 int main()
46 {
47     int t;
48     scanf("%d",&t);
49     while(t--)
50     {
51         int n,cnt=0;
52         double x1,x2,y1,y2;
53         scanf("%d",&n);
54         for(int i=1;i<=n;i++)
55         {
56             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
57             a[++cnt]=seg(x1,x2,y1,1);
58             x[cnt]=x1;
59             a[++cnt]=seg(x1,x2,y2,-1);
60             x[cnt]=x2;
61         }
62         sort(x+1,x+1+cnt);
63         sort(a+1,a+1+cnt);
64         int k=1;
65         for(int i=2;i<=cnt;i++)
66             if(x[i]!=x[i-1])
67                 x[++k]=x[i];
68         memset(col,0,sizeof(col));
69         memset(sum1,0,sizeof(sum1));
70         memset(sum2,0,sizeof(sum2));
71         double ans=0;
72         for(int i=1;i<cnt;i++)
73         {
74             int l=lower_bound(x+1,x+1+k,a[i].l)-x;
75             int r=lower_bound(x+1,x+1+k,a[i].r)-x-1;
76             Update(l,r,a[i].s,1,k,1);
77             ans+=sum2[1]*(a[i+1].h-a[i].h);
78         }
79         printf("%.2f\n",ans);
80     }
81     return 0;
82 }