题目大意：
给你n个矩形，求出它们面积的并。
解题分析：
此题主要用到了扫描线的思想，现将各个矩形的横坐标离散化，然后用它们离散化后的横坐标（相当于将矩形的每条竖线投影在x轴上，然后将它们从0~n-1标号），并且利用这些标好的号建线段树，线段树的每个叶子节点表示离散化后的横坐标(比如从左往右数第一个叶子节点，它的区域表示的就是第0个竖线)。建好数后，就用扫描线从下至上进行扫描，若为下边界，则add[rt]+=1,若为上边界，则add[rt]-=1;扫描线到上面一个边界时，就用高度差*整个区域内的有效长度，即为这一部分矩形的面积。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define Lson rt<<1,l,mid
#define Rson rt<<1|1,mid+1,r //线段树的每一个节点都有对应的add和sum值
const int M =;
int add[M<<]; //add为区间标记,标记这段区间是否有效(是不是对求面积做出贡献的一段)
double sum[M<<],x[M<<]; //sum表示这段区间内总共的有效长度 struct node{
int cnt; //cnt=1为下边，cnt=-1为上边
double l,r,h; //分别记录线段的左端，右端和高度
node(){}
node(double a,double b,double c,int d):l(a),r(b),h(c),cnt(d){}
friend bool operator <(node tmp1,node tmp2){
return tmp1.h<tmp2.h; //从下往上扫，所以将h从小到大排序
}
}s[M<<];
void Pushup(int rt,int l,int r){
if(add[rt])sum[rt]=x[r+]-x[l]; //如果这段区域add不为0，则说明这段区域全部有效,由于原来查询的时候是左闭右开，所以这里的真实区域要+1
else if(l==r)sum[rt]=;
else sum[rt]=sum[rt<<]+sum[rt<<|]; //求出这段区域的真正有效长度
}
void update(int rt,int l,int r,int L,int R,int cor){
if(L<=l&&r<=R){
add[rt]+=cor;
Pushup(rt,l,r); //由于add标记改变了，所以更新一下tr[rt]的sum值
return;
}
int mid=(l+r)>>;
if(L<=mid)update(Lson,L,R,cor);
if(R>mid)update(Rson,L,R,cor);
Pushup(rt,l,r); //用递归更新一下路径上的所有sum值
} int main(){
int n,ncase=;
while(scanf("%d",&n)!=EOF,n){
double a,b,c,d;
int m=;
for(int i=;i<n;i++){
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
x[m]=a;
s[m++]=node(a,c,b,); //矩形下面那条边
x[m]=c;
s[m++]=node(a,c,d,-);
}
sort(x,x+m);
sort(s,s+m);
memset(add,,sizeof(add)); //这两个memset相当于建树
memset(sum,,sizeof(sum));
int k=;
for(int i=;i<m;i++){
if(x[i]!=x[i-]){
x[k++]=x[i]; //去重
}
}
//0~k-1为离散化后的线段树sum[1]所对应的区域
double ans=;
for(int i=;i<m-;i++){ //这里只需要循环m-1次就行，因为一共有m-1段面积
int l=lower_bound(x,x+k,s[i].l)-x;
int r=lower_bound(x,x+k,s[i].r)-x-; //为避免边的边界重复，我们选取左闭右开区间,所以r要减1
update(,,k-,l,r,s[i].cnt);
ans+=sum[]*(s[i+].h-s[i].h); //sum[1]代表 X(min)~X(max)区域内的有效线段长度，即需要乘以高度差的线段长度
}
printf("Test case #%d\n", ++ncase);
printf("Total explored area: %.2lf\n\n", ans);
}
return ;
}
2018-07-25