HDU 1542 Atlantis（线段的树应用——求矩形的面积并）

题目大意：给定每个矩形的对角线的两个端点，让你求这些矩形的面积的并集，即重叠的不能重复计算！

题目分析：这题就是典型的线段树求面积并！

离散化：对所有节点的Y进行升序排序，然后以Y的位置建树，就是指，在线段树里面，左右节点的实际意义就是指这个线段在Y的升序数组里的位置，但是我们把lf,rf赋值为这个线段左右端点的具体值！这就是离散化！

建树的细节：树的每个节点有lf,rf,cover,lenth，分别指这个节点所表示的线段的左端点，右端点，被覆盖的次数（在这里覆盖的次数是为了 区分重叠矩形的情况下，高度的正确存取，因为一个矩形对Y轴的覆盖是以他的左边开始，右边结束的，所以当插入左边的时候，我们把cover+1，右边的时候把cover-1，说明这个矩形对Y的覆盖已经结束，计算下一个矩形时，不会错误的把我这个矩形的高度当作下一个矩形的高度！），lenth指这个区间被矩形覆盖的长度即矩形的实际高度！；

插入的时候，先把存放节点的数组，对X进行升序排序！然后顺次插入，分别计算！

代码如下+部分注释：

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;

struct tree{
	double lf,rf,lenth;
	int cover;
}s[4000];//树节点定义

double x1,y1,x2,y2,ym[1000];

struct node{
	double x,y1,y2;
	int flag;
}t[4000];//存放矩形左，右边的节点

int cmp1(double x,double y){
	return x<y;
}

int cmp2(struct node a,struct node b){
	return a.x<b.x;
}

void len(int n){
	if(s[n].cover>0)
		s[n].lenth=s[n].rf-s[n].lf;
	else
		s[n].lenth=s[2*n+1].lenth+s[2*n].lenth;
}

int Build(int x,int y,int num){
	s[num].lf=ym[x];
	s[num].rf=ym[y];
	s[num].lenth=s[num].cover=0;
	if(x+1==y)
		return 0;
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid,y,num+num+1);
}

int modify(int num,struct node n){
	if(s[num].lf==n.y1&&s[num].rf==n.y2){
		s[num].cover+=n.flag;
		len(num);
		return 0;
	}
	if(n.y1>=s[num+num].rf)
		modify(num+num+1,n);
	else if(n.y2<=s[num+num+1].lf)
		modify(num+num,n);
	else{
		struct node vs=n;
		vs.y2=s[num+num].rf;
		modify(num+num,vs);
		vs=n;
		vs.y1=s[num+num+1].lf;
		modify(num+num+1,vs);
	}
	len(num);//往上更新线段被覆盖的实际长度！如果节点的cover>0 该区间节点的被覆盖就是，区间的整体程度，否则，该区间节点的被覆盖等于左右节点被覆盖长度的和！
}

int main(){
	int cas,i,j,k=1;
	double sum;
	while(cin>>cas,cas){
		for(j=i=1;i<=cas;i++,j+=2){
			scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
			ym[j]=y1;
			t[j].x=x1;
			t[j].y1=y1;
			t[j].y2=y2;
			t[j].flag=1;
			ym[j+1]=y2;
			t[j+1].x=x2;
			t[j+1].y1=y1;
			t[j+1].y2=y2;
			t[j+1].flag=-1;
		}
		sort(ym+1,ym+j,cmp1);
		sort(t+1,t+j,cmp2);
		Build(1,j-1,1);
		modify(1,t[1]);
		sum=0;
		for(i=2;i<j;i++){
			sum+=(t[i].xt[i-1].x)*s[1].lenth;
                      //每插入完一个点，就以他后继的点求面积！
			modify(1,t[i]);
		}
		printf("Test case #%d\n",k);
		printf("Total explored area: %.2lf\n\n",sum);
		k++;
	}
	return 0;
}