题目：poj1151
建议先参考参考别的扫描线文档。
考虑这样一些矩形：
拿一根扫描线从左往右扫，扫描线被矩形覆盖的长度会变化当扫过矩形的左右边界时。
我们就剥离出来左右边界。我们把所有的 (y) 值都保存下来离散化。
我们拿线段树维护扫描线。线段树结点应保存从第几个 (y) 开始到第几个 (y) 结束，有多少个区间是有覆盖的。因此，维护 (l) 个到 (r) 个的结点，它的子结点是 (l sim mid) 和 (mid sim r)。这是与普通线段树的差别之一。
应该打上懒标记的，只不过我没搞
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int n, casecnt, cnt, m;
double ans, uu, vv, ww, zz, yy[205];
struct Line{
double xx, yu, yv;
int fla;
}li[205];
struct Node{
int cov;
double val;
void clr(){
cov = val = 0;
}
}nd[805];
bool cmp(Line x, Line y){
return x.xx<y.xx;
}
void build(int o, int l, int r){
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(l+1==r) nd[o].clr();
else{
if(l<=mid) build(lson, l, mid);
if(mid<=r) build(rson, mid, r);
}
}
void qwq(int o, int l, int r, const Line &x){
nd[o].cov += x.fla;
if(!nd[o].cov) nd[o].val = 0.0;
else nd[o].val = yy[r] - yy[l];
}
void update(int o, int l, int r, const Line &x){
if(l+1==r) qwq(o, l, r, x);
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(yy[mid]>x.yu) update(lson, l, mid, x);
if(yy[mid]<x.yv) update(rson, mid, r, x);
nd[o].val = nd[lson].val + nd[rson].val;
}
}
int main(){
while(scanf("%d", &n)!=EOF){
if(!n) break;
casecnt++;
ans = 0.0;
cnt = m = 0;
for(int i=1; i<=n; i++){
scanf("%lf %lf %lf %lf", &uu, &vv, &ww, &zz);
yy[++cnt] = vv;
li[cnt].xx = uu; li[cnt].yu = vv; li[cnt].yv = zz; li[cnt].fla = 1;
yy[++cnt] = zz;
li[cnt].xx = ww; li[cnt].yu = vv; li[cnt].yv = zz; li[cnt].fla = -1;
}
sort(yy+1, yy+1+cnt);
m = unique(yy+1, yy+1+cnt) - yy - 1;
sort(li+1, li+1+cnt, cmp);
build(1, 1, m);
for(int i=1; i<=cnt; i++){
ans += nd[1].val * (li[i].xx - li[i-1].xx);
update(1, 1, m, li[i]);
}
printf("Test case #%d
Total explored area: %.2f
", casecnt, ans);
}
return 0;
}