題目鏈接：點擊打開鏈接
題目描寫敘述：給定一些矩形，求這些矩形的總面積。假設有重疊。僅僅算一次
解題思路：掃描線+線段樹+離散（代碼從上往下掃描）
代碼：
#include<cstdio>
#include <algorithm>
#define MAXN 110
#define LL ((rt<<1)+1)
#define RR ((rt<<1)+2)
using namespace std;
int n;
struct segment{double l,r,h;int f;bool operator<(const segment& b)const{return h>b.h;}
}sg[2*MAXN];
double pos[2*MAXN];
int id;
void addSegment(double x1,double y1,double x2,double y2){sg[id].l=x1;sg[id].r=x2;sg[id].h=y1;sg[id].f=1;pos[id++]=x1;sg[id].l=x1;sg[id].r=x2;sg[id].h=y2;sg[id].f=-1;pos[id++]=x2;
}
int binary(double key,int low,int high){while(low<=high){int mid=(low+high)/2;if(pos[mid]==key)return mid;else if(key<pos[mid])high=mid-1;elselow=mid+1;}return -1;
}
struct Tree{int l,r;int cover;double len;
}tree[8*MAXN];
void build(int rt,int l,int r){tree[rt].l=l;tree[rt].r=r;tree[rt].cover=0;tree[rt].len=0;if(l==r-1)return;int mid=(l+r)>>1;build(LL,l,mid);build(RR,mid,r);
}
void pushup(int rt){if(tree[rt].cover)tree[rt].len=pos[tree[rt].r]-pos[tree[rt].l];else if(tree[rt].l==tree[rt].r-1)tree[rt].len=0;elsetree[rt].len=tree[LL].len+tree[RR].len;
}
void update(int rt,int l,int r,int f){if(tree[rt].l==l&&tree[rt].r==r){tree[rt].cover+=f;pushup(rt);return;}int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid)update(LL,l,r,f);else if(l>=mid)update(RR,l,r,f);else{update(LL,l,mid,f);update(RR,mid,r,f);}pushup(rt);
}
int main(){int Case=0;while(scanf("%d",&n)!=EOF&&n!=0){id=0;double x1,y1,x2,y2;for(int i=0;i<n;++i){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);addSegment(x1,y1,x2,y2);}n=(n<<1);sort(sg,sg+n);sort(pos,pos+n);int m=1;for(int i=1;i<n;++i)if(pos[i]!=pos[i-1])pos[m++]=pos[i];build(0,0,m-1);double ans=0;int l=binary(sg[0].l,0,m-1);int r=binary(sg[0].r,0,m-1);update(0,l,r,sg[0].f);for(int i=1;i<n;i++){ans+=(sg[i-1].h-sg[i].h)*tree[0].len;l=binary(sg[i].l,0,m-1);r=binary(sg[i].r,0,m-1);update(0,l,r,sg[i].f);}printf("Test case #%d\n",++Case);printf("Total explored area: %.2f\n\n",ans);}return 0;
}
