HDu 1542 Atlantis面積及び線分ツリー走査線

#include<cstdio>
#include<algorithm>
#include<cstring>
#define LMT 202
#define left l,m,x<<1
#define right m+1,r,x<<1|1
using namespace std;
//shit double int    
struct line
{
    double h,l,r;
    int d;
    line(void){}
    line(double y,double x1,double x2,int dd):h(y),l(x1),r(x2),d(dd){}
    bool operator<(const line &y)const
    {
        return h<y.h;
    }
}ln[LMT];
double sum[LMT<<2],X[LMT];
int cnt[LMT<<2];
void pushup(int l,int r,int x)//             ，      
{
    if(cnt[x])sum[x]=X[r+1]-X[l];//          ，                 
    else if(l==r)sum[x]=0;
    else sum[x]=sum[x<<1]+sum[x<<1|1];
    /*****
           l,r-1   ，   l,r,                ，  
        l==r   ，     sum[x<<1],          ，         
       ，   ，         ，  ，        
    *****/
}
void update(int L,int R,int c,int l,int r,int x)
{
    if(L<=l&&r<=R)
    {
        cnt[x]+=c;
        pushup(l,r,x);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m)update(L,R,c,left);
    if(R>m)update(L,R,c,right);
    pushup(l,r,x);
}
int equry(double key,int n)//    
{
    int m,l=0,r=n;
    while(l<=r)
    {
        m=(l+r)>>1;
        if(key==X[m])return m;
        if(key>X[m])l=m+1;
        else r=m-1;
    }
    return -1;
}
int main(void)
{
    int n,k,I=1;
    double ans;
    while(~scanf("%d",&n)&&n>0)
    {
        double a,b,c,d;
        int num=0;
        ans=0;
        while(n--)
        {
           scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
           ln[num]=line(b,a,c,1);
           X[num]=a;
           num++;
           ln[num]=line(d,a,c,-1);
           X[num]=c;
           num++;
        }
        sort(ln,ln+num);
        sort(X,X+num);
        memset(sum,0,sizeof(sum));
        memset(cnt,0,sizeof(cnt));
        k=1;
        for(int i=1;i<num;i++)
        if(X[i]!=X[i-1])X[k++]=X[i];
        for(int i=0;i<num-1;i++)
        {
            int l=equry(ln[i].l,k-1),r=equry(ln[i].r,k-1)-1;
            if(l<=r)//       
            {
              update(l,r,ln[i].d,0,k-1,1);//       
              ans+=sum[1]*(ln[i+1].h-ln[i].h);
            }
        }
        printf("Test case #%d
Total explored area: %.2lf

",I++,ans);
    }
    return 0;
}