二維平面有n個(gè)平行于坐標(biāo)軸的矩形,現(xiàn)在要求出這些矩形的總面積.
輸入：每個(gè)長(zhǎng)方形左下角和右上角的坐標(biāo)。

image.png

所謂掃描線，就是從下到上將圖形分開，不管原來怎么重疊，現(xiàn)在只當(dāng)作幾個(gè)長(zhǎng)方形看。如圖：

image.png

具體細(xì)節(jié)：
1.離散化：
輸入的兩個(gè)點(diǎn)橫坐標(biāo)為小數(shù)，再線段樹中需要離散化(排序，去重）

double a[maxn],b[maxn],c[maxn],d[maxn],mp[maxn*2+1];
unordered_map<double,int> _hash;

for(int i = 0 ; i < n ; i++){
            scanf("%lf%lf%lf%lf",&a[i],&b[i],&c[i],&d[i]);
            mp[k++] = a[i];
            mp[k++] = c[i];
        }
        sort(mp,mp+k);
        en = unique(mp,mp+k)-mp;
        for(int i = 0 ; i < en ; i++){
            _hash[mp[i]] = i+1;
         
        }
        for(int i = en ; i >= 1 ; i--){
            mp[i] = mp[i-1];
           
        }
        mp[en+1] = mp[en];

2.按照h排序，即每個(gè)點(diǎn)的y坐標(biāo)。
這里用pair，加到線段樹中，入邊++，出邊--。

typedef pair<double,int> pi;
typedef pair<int,int> pk;
typedef pair<pi,pk> pii;
pii tr[maxn];

for(int i =0 ; i < n ; i++){
            tr[i*2] = make_pair(make_pair(b[i],1),make_pair(_hash[a[i]],_hash[c[i]]));
            tr[i*2+1] = make_pair(make_pair(d[i],-1),make_pair(_hash[a[i]],_hash[c[i]]));
        }
        sort(tr,tr+n*2);

3.線段樹維護(hù)標(biāo)記lz，-1為左子樹右子樹區(qū)間中，作為入邊和出邊不同的時(shí)候。>0為這個(gè)區(qū)間被覆蓋，即重新劃線之后這段區(qū)間是新的長(zhǎng)方形部分。
所以push_down和push_up函數(shù)要討論一下lz的值

void push_down(int rt,double lon1,double lon2){
    if(tree[rt].lz!=-1){
        tree[rt*2].lz += tree[rt].lz;
        if(tree[rt*2].lz != 0)tree[rt*2].sum = lon1;
        else    tree[rt*2].sum = 0;
        tree[rt*2+1].lz += tree[rt].lz;
        if(tree[rt*2+1].lz != 0) tree[rt*2+1].sum  = lon2;
        else tree[rt*2+1].sum =0;
        tree[rt].lz = 0;
    }
}
void push_up(int rt){
    if(tree[rt*2].lz == -1 || tree[rt*2+1].lz == -1)
        tree[rt].lz = -1;
    else if(tree[rt*2].lz != tree[rt*2+1].lz)
        tree[rt].lz = -1;
    else
        tree[rt].lz = tree[rt*2].lz;
    tree[rt].sum = tree[rt*2].sum+tree[rt*2+1].sum;
}

4.離散化之后不能單純的sum了，因?yàn)檎嬲拈L(zhǎng)度為mp[r]-mp[l],所以求的時(shí)候要update(l,r-1)
update函數(shù)里求sum則是

  push_down(rt,mp[m+1]-mp[l],mp[r+1]-mp[m+1]);

保證最后結(jié)果是對(duì)的。

#include <unordered_map>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 510;
typedef pair<double,int> pi;
typedef pair<int,int> pk;
typedef pair<pi,pk> pii;
int n,en;
pii tr[maxn];
int k;
double a[maxn],b[maxn],c[maxn],d[maxn],mp[maxn*2+1];
unordered_map<double,int> _hash;
struct node{
    int lz;
    double sum;
}tree[maxn*2*4+10];
void init(){
        for(int i = 0 ; i < n ; i++){
            scanf("%lf%lf%lf%lf",&a[i],&b[i],&c[i],&d[i]);
            mp[k++] = a[i];
            mp[k++] = c[i];
        }
        sort(mp,mp+k);
        en = unique(mp,mp+k)-mp;
        for(int i = 0 ; i < en ; i++){
            _hash[mp[i]] = i+1;
            //mp[i]:value of x(double)
        }
        for(int i = en ; i >= 1 ; i--){
            mp[i] = mp[i-1];
            //mp[i]:value of x(double)
        }
        mp[en+1] = mp[en];
        for(int i =0 ; i < n ; i++){
            tr[i*2] = make_pair(make_pair(b[i],1),make_pair(_hash[a[i]],_hash[c[i]]));
            tr[i*2+1] = make_pair(make_pair(d[i],-1),make_pair(_hash[a[i]],_hash[c[i]]));
        }
        sort(tr,tr+n*2);
}
void build(int l,int r,int rt){
    if(l == r){
        tree[rt].lz = 0;
        tree[rt].sum = 0.0;
        return ;
    }
    int m  = (l+r)/2;
    build(lson);
    build(rson);
    tree[rt].lz = 0;
    tree[rt].sum = 0.0;
}
void push_down(int rt,double lon1,double lon2){
    if(tree[rt].lz!=-1){
        tree[rt*2].lz += tree[rt].lz;
        if(tree[rt*2].lz != 0)tree[rt*2].sum = lon1;
        else    tree[rt*2].sum = 0;
        tree[rt*2+1].lz += tree[rt].lz;
        if(tree[rt*2+1].lz != 0) tree[rt*2+1].sum  = lon2;
        else tree[rt*2+1].sum =0;
        tree[rt].lz = 0;
    }
}
void push_up(int rt){
    if(tree[rt*2].lz == -1 || tree[rt*2+1].lz == -1)
        tree[rt].lz = -1;
    else if(tree[rt*2].lz != tree[rt*2+1].lz)
        tree[rt].lz = -1;
    else
        tree[rt].lz = tree[rt*2].lz;
    tree[rt].sum = tree[rt*2].sum+tree[rt*2+1].sum;
}
void update(int L,int R,int l,int r,int rt,int ch){
    if(L <= l && r <= R){
        if(tree[rt].lz != -1){
            tree[rt].lz += ch;
            if(tree[rt].lz != 0)tree[rt].sum = (mp[r+1]-mp[l]);
            else    tree[rt].sum = 0.0;
            return ;
        }
        
    }
    int m = (l+r)/2;
    push_down(rt,mp[m+1]-mp[l],mp[r+1]-mp[m+1]);

    if(L <= m)  update(L,R,lson,ch);s
    if(R > m)  update(L,R,rson,ch);
    push_up(rt);
}

void sov(){
    double ans = 0;
    build(1,en,1);
    for(int i = 0 ; i < n*2-1 ; i++){
        double  h = tr[i].first.first;
        update(tr[i].second.first,tr[i].second.second-1,1,en,1,tr[i].first.second);
        ans += tree[1].sum*(tr[i+1].first.first-h);
    }
    printf("%.2lf\n\n",ans);
}
int main(){
    int T = 1;
    while(scanf("%d",&n)!= EOF && n){
        init();
        printf("Test case #%d\nTotal explored area: ",T);
        sov();
        T++;
    }

}