矩形面积交（线段树+扫描线）

59 阅读 0 评论 39 点赞

我是靠谱客的博主俊秀超短裙，最近开发中收集的这篇文章主要介绍矩形面积交（线段树+扫描线），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

我们要计算被覆盖两次或以上的部分面积，我们在线段树节点中增设了一个变量，more，其中len表示该该区间内被覆盖了1次或以上的长度，more表示被覆盖了2次或以上的长度

怎么计算最后的面积的？一样的道理，从下往上扫描矩形，每次添加一条矩形上下边，然后看看t[1].more是多少，再乘上高度差。因为t[1]表示了总区间，而more表示被覆盖两次或以上的长度，即计算时我们忽略掉只被覆盖一次的长度

问题的关键变为怎么计算一个节点的more

分情况讨论

1.cnt>1 : 说明该区间被覆盖两次或以上，那么长度就可以直接计算，就是该区间的长度

剩下的情况就是cnt=1或cnt=0

2.先看叶子节点，因为是叶子没有孩子了，所以被覆盖两次货以上的长度就是0（无论cnt=1或cnt=0都是0，因为是叶子。。。）

3.不是叶子节点，且cnt=1.注意这里，cnt=1确切的意义是什么，应该是，可以确定，这个区间被完全覆盖了1次，而有没有被完全覆盖两次或以上则不知道无法确定，那么怎么怎么办了，只要加上t[lch].len + t[rch].len 即，看看左右孩子区间被覆盖了一次或以上的长度，那么叠加在双亲上就是双亲被覆盖两次或以上的长度

3.不是叶子节点，且cnt=0，确切的意义应该是不完全不知道被覆盖的情况（不知道有没有被覆盖，被覆盖了几次，长度是多少都不知道），这种情况，只能由其左右孩子的信息所得

t[lch].more + t[rch].more , 即直接将左右孩子给覆盖了两次或以上的长度加起来，这样才能做到不重不漏

附上代码：


#include<bits/stdc++.h>
 
using namespace std;
 
const int MAXN=2020;
 
struct Node{
    int l,r;
    int cover;
    double lf,rf;
    double len;//覆盖一次以上的长度
    double more;//覆盖两次以上的长度
}segTree[MAXN*4];
 
struct Line{
    double y,x1,x2;
    double f;
}line[MAXN];
 
double x[MAXN];
 
bool cmp(Line a,Line b){
    return a.y<b.y;
}
 
void Build(int i,int l,int r){
    segTree[i].l=l;
    segTree[i].r=r;
    segTree[i].len=0;
    segTree[i].more=0;
    segTree[i].lf=x[l];
    segTree[i].rf=x[r];
    if(l+1==r)return;
    int mid=(l+r)>>1;
    Build(i<<1,l,mid);
    Build((i<<1)|1,mid,r);
}

void calen(int i){
    if(segTree[i].cover>=2){
        segTree[i].more=segTree[i].len=segTree[i].rf-segTree[i].lf;
        return;
    }else if(segTree[i].cover==1){
        segTree[i].len=segTree[i].rf-segTree[i].lf;
        if(segTree[i].l+1==segTree[i].r){
            segTree[i].more=0;
        }else{
            segTree[i].more=segTree[i<<1].len+segTree[(i<<1)|1].len;
        } 
    }else{
        if(segTree[i].l+1==segTree[i].r){
            segTree[i].len=segTree[i].more=0;
        }else{
            segTree[i].len=segTree[i<<1].len+segTree[(i<<1)|1].len;
            segTree[i].more=segTree[i<<1].more+segTree[(i<<1)|1].more;
        }
    }
}

void update(int i,Line e){
    if(e.x1==segTree[i].lf&&segTree[i].rf==e.x2){
        segTree[i].cover+=e.f;
        calen(i);
        return;
    }
    if(e.x2<=segTree[i<<1].rf){
        update(i<<1,e);
    }else if(e.x1>=segTree[(i<<1)|1].lf){
        update((i<<1)|1,e);
    }else{
        Line temp=e;
        temp.x2=segTree[i<<1].rf;
        update(i<<1,temp);
        temp=e;
        temp.x1=segTree[(i<<1)|1].lf;
        update((i<<1)|1,temp);
    }
    calen(i);
}
int main(){
    int T;
    int n;
    double x1,y1,x2,y2;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int t=1;
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[t].y=y1;
            line[t].x1=x1;
            line[t].x2=x2;
            line[t].y=y1;
            line[t].f=1;
            x[t]=x1;
            t++;
 
            line[t].x1=x1;
            line[t].x2=x2;
            line[t].y=y2;
            line[t].f=-1;
            x[t]=x2;
            t++;
        }
        sort(line+1,line+t,cmp);
        sort(x+1,x+t);
        int len=unique(x+1,x+t)-x;
        Build(1,1,len-1);
        update(1,line[1]);
        double ans=0;
        for(int i=2;i<t;i++){
            ans+=segTree[1].more*(line[i].y-line[i-1].y);
            update(1,line[i]);
        }
        printf("%.2lfn",ans);
    }
    return 0;
}