POJ 1151扫描线 线段树维护

思路：

1. 将矩形拆成上界和下界，每次循环执行一条扫描线（矩形的一条边，不是同一y坐标的边的总和）
2. 通过线段树维护当前矩形的长度。

#include <iostream>
#include <algorithm>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1

const int maxn = 1e5+500;

struct seg{
    double l,r,h;
    int f;
    seg(){}
    seg(double l,double r,double h,int f):l(l),r(r),h(h),f(f){}
    bool operator<(const seg& a){return h<a.h;}
}edge[maxn];
struct node{double len;int tag;}tree[maxn<<2];
int n,tot;
double x[maxn];

inline void pushdown(int l,int r,int rt){
    if(tree[rt].tag) tree[rt].len = x[r+1]-x[l];
    else if(l==r) tree[rt].len = 0;
    else tree[rt].len = tree[ls].len + tree[rs].len;
}

void update(int l,int r,int rt,int L,int R,int k){
    if(L<=l&&r<=R){
        tree[rt].tag += k;
        pushdown(l,r,rt);
        return ;
    }
    int mid = l+r>>1;
    if(L<=mid) update(l,mid,ls,L,R,k);
    if(mid<R) update(mid+1,r,rs,L,R,k);
    pushdown(l,r,rt);
}

int main(){
    int _=1;
    while(scanf("%d",&n)!=EOF&&n){
        tot=0;
        for(int i=0;i<maxn<<2;i++) 
            tree[i].len = tree[i].tag = 0;	//初始化
        for(int i=1;i<=n;i++){
            double x1,x2,y1,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            x[++tot] = x1 , edge[tot] = seg(x1,x2,y1,1);
            x[++tot] = x2 , edge[tot] = seg(x1,x2,y2,-1);
        }
        sort(x+1,x+tot+1);
        sort(edge+1,edge+tot+1);			//对扫描线排序
        int cnt = unique(x+1,x+tot+1)-x-1;	//离散化
        double res = 0;
        for(int i=1;i<=tot;i++){
            int l = lower_bound(x+1,x+cnt+1,edge[i].l)-x;
            int r = lower_bound(x+1,x+cnt+1,edge[i].r)-x-1;
            update(1,cnt,1,l,r,edge[i].f);
            res += tree[1].len*(edge[i+1].h-edge[i].h);//更新答案
        }
        printf("Test case #%d
Total explored area: %.2lf 

",_++,res);
    }
    return 0;
}