hdu1542 矩形面积并（扫描线）

二维平面有n个平行于坐标轴的矩形,现在要求出这些矩形的总面积.
输入：每个长方形左下角和右上角的坐标。

image.png

所谓扫描线，就是从下到上将图形分开，不管原来怎么重叠，现在只当作几个长方形看。如图：

image.png

具体细节：
1.离散化：
输入的两个点横坐标为小数，再线段树中需要离散化(排序，去重）

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排序，即每个点的y坐标。
这里用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.线段树维护标记lz，-1为左子树右子树区间中，作为入边和出边不同的时候。>0为这个区间被覆盖，即重新划线之后这段区间是新的长方形部分。
所以push_down和push_up函数要讨论一下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了，因为真正的长度为mp[r]-mp[l],所以求的时候要update(l,r-1)
update函数里求sum则是

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

保证最后结果是对的。

#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++;
    }

}