扫描线-离散化-矩形面积交

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

这题基本和上一题求矩形面积并一样：POJ1151 Atlantis（线段树，扫描线，离散化,矩形面积并）

我们要做的是这次记录覆盖两次或者两次以上的区间，求矩形的面积交

用cnt来记录覆盖过的次数

要做的是在向下更新的时候：

1. 如果当前的cnt>1的时候，证明覆盖过两次，直接计算
2. 如果当前左右区间相等，那么s就肯定为0
3. 如果当前cnt==1，那么就证明这个区间已经被完全覆盖过了，我们要使它覆盖两次，只需要在它的左右儿子里面找到覆盖过的区间，就可以使他变成覆盖两次的
4. 对于其他情况，求所有儿子的值求得

HDU1255 覆盖的面积(线段树，离散化，扫描线，矩形面积交)

#define mem(a,b) memset(a,b,sizeof(a))  
#define inf 0x3f3f3f3f  
#define N 2200  
#define ll long long  
using namespace std;  
#define lson l,m,rt<<1  
#define rson m+1,r,rt<<1|1  
struct Seg  
{  
    double l,r,h;  
    int f;  
    Seg() {}  
    Seg(double a,double b,double c,int d):l(a),r(b),h(c),f(d) {}  
    bool operator < (const Seg &cmp) const  
    {  
        return h<cmp.h;  
    }  
} e[N];  
struct node  
{  
    int cnt;  
    double len,s;  
} t[N<<2];  
double X[N];  
void pushdown(int l,int r,int rt)  
{  
    if(t[rt].cnt)  
        t[rt].len=X[r+1]-X[l];  
    else if(l==r)  
        t[rt].len=0;  
    else  
        t[rt].len=t[rt<<1].len+t[rt<<1|1].len;  
    if(t[rt].cnt>1)  
        t[rt].s=X[r+1]-X[l];  
    else if(l==r)  
        t[rt].s=0;  
    else if(t[rt].cnt==1)  
        t[rt].s=t[rt<<1].len+t[rt<<1|1].len;  
    else  
        t[rt].s=t[rt<<1].s+t[rt<<1|1].s;  
}  
void update(int L,int R,int l,int r,int rt,int val)  
{  
    if(L<=l&&r<=R)  
    {  
        t[rt].cnt+=val;  
        pushdown(l,r,rt);  
        return;  
    }  
    int m=(l+r)>>1;  
    if(L<=m) update(L,R,lson,val);  
    if(R>m) update(L,R,rson,val);  
    pushdown(l,r,rt);  
}  
int main()  
{  
    int n,q;  
    double a,b,c,d;  
    scanf("%d",&q);  
    while(q--)  
    {  
        scanf("%d",&n);  
        mem(t,0);  
        int num=0;  
        for(int i=0; i<n; i++)  
        {  
            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);  
            X[num]=a;  
            e[num++]=Seg(a,c,b,1);  
            X[num]=c;  
            e[num++]=Seg(a,c,d,-1);  
        }  
        sort(X,X+num);  
        sort(e,e+num);  
        int m=unique(X,X+num)-X;  
        double ans=0;  
        for(int i=0; i<num; i++)  
        {  
            int l=lower_bound(X,X+m,e[i].l)-X;  
            int r=lower_bound(X,X+m,e[i].r)-X-1;  
            update(l,r,0,m,1,e[i].f);  
            ans+=t[1].s*(e[i+1].h-e[i].h);  
        }  
        printf("%.2lf\n",ans);  
    }  
    return 0;  
}