题解 | #Atlantis#

思路

这道题是扫描线线段树的板子题，具体的处理方法：
(1)每个矩形的上下边加入扫描线并标记，下边标记为1，上边标记为-1
(2)让扫描线从从低到高排序，而矩形的左右边从小到大排序
(3)考虑数据范围，我们进行离散化处理
(3)建立线段树，那么区间可表示为区域的y1,y2，以及长度。
(4)遍历所有相邻左右边，每次通过线段树询问出高度，然后面积相加。
注意我们这里要维护的是线段长度而非点的值，所以我们要对线段树进行修改，即左孩子的右值=右孩子的左值，这样才能使维护不出现缝隙。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
//#define int long long
using namespace std;
const int maxn=205;
typedef long long ll;

struct L{
    double x,y1,y2,flag;
    L(double X=0,double Y1=0,double Y2=0,double T=0){
        x=X,y1=Y1,y2=Y2,flag=T;
    }
}line[maxn];

struct T{
    int l,r; //左右区间 
    double len; //长度 
    int lazy;//标记 
}t[maxn<<2];

bool cmp(L a,L b){
    return a.x<b.x;
}

int n,idx,ans,cnt;
double x1,x2,y1,y2; 
double seg[maxn]; //用于存放扫描线 
map<double,int>mp; //用于离散化 

void build(int p,int l,int r){ //建树 
    t[p].l=l;t[p].r=r;t[p].len=0;t[p].lazy=0;
    if(l==r) return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

void update(int p){ //更新长度
    if(t[p].lazy) t[p].len=seg[t[p].r+1]-seg[t[p].l];
    else if(t[p].l==t[p].r) t[p].len=0;
    else t[p].len=t[p<<1].len+t[p<<1|1].len;
}

void change(int p,int l,int r,int k){
    if(l<=t[p].l&&t[p].r<=r){ //扫描线的y就在区间中 
        t[p].lazy+=k; //打上标签 
        update(p); //更新区域高度 
        return; 
    }
    int mid=t[p].l+t[p].r>>1; 
    if(l<=mid) change(p<<1,l,r,k);
    if(r>mid) change(p<<1|1,l,r,k);
    update(p);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    while(n){
        cnt=0; //清空线段 
        for(int i=1;i<=n;i++){
            cin>>x1>>y1>>x2>>y2;
            line[++cnt]=L(x1,y1,y2,1); //记录竖线 
            seg[cnt]=y1; //记录扫描线 
            line[++cnt]=L(x2,y1,y2,-1);
            seg[cnt]=y2;
        }
        sort(line+1,line+1+cnt,cmp); //排序 
        sort(seg+1,seg+1+cnt); 
        int m=unique(seg+1,seg+1+cnt)-(seg+1); //去重后有m段扫描线
        for(int i=1;i<=m;i++) mp[seg[i]]=i;
        build(1,1,m); //建树
        double ans=0;
        for(int i=1;i<cnt;i++){ //遍历每一条竖线
            int L=mp[line[i].y1],R=mp[line[i].y2]-1;//区域的上下边 
            change(1,L,R,line[i].flag); //查询并更新区域的高 
            ans+=t[1].len*(line[i+1].x-line[i].x); //累加区域面积 
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n",++idx,ans); 
        cin>>n;
    }
    return 0;
}