HDU 1255 （覆盖的面积） 典型的求交面积

题目大意：给对角线 求覆盖次数至少为2次的面积

思路：首先把Y离散化，从小到大排序，然后以Y在数组种存放的位置，建树。但是线段树的lf,rf,存放的是Y的实际值，这就是离散化。

然后 在节点里用cover记录被覆盖的次数，lenth表示至少被覆盖一次的区间长度,inlenths,记录被覆盖两次以上的区间长度，这里比起求矩形的并面积，就是多了个记录与更新至少覆盖两次的情况的操作！
建树：跟求区间的并 区别不大，就是多了一个对inlenths的初始化。

更新：从上到下遍历，找到需要更新区间，如果是矩形的左边，cover加1，表示在这个高度，多了个区间覆盖在其之上，如果是矩形的右边则减1，说明，少了个区间覆盖在这个高度范围内，也就是矩形的覆盖，更新当前区间的lenth,如果cover>0则lenth等于该区间的整体长度，否则等于左右子树的覆盖长度，然后更新inlenths的长度，当cover>2,表明这个高度有2个以上矩形覆盖，即把inlenths赋值为当前区间的整体长度，如果cover=1说明这个区间整体只被覆盖一次，那么inlenths的值就等于左右子区间被覆盖一次以上的长度，因为整体的已经被覆盖了一次，只有子区间有被覆盖过大于等于一次，那么该长度也被覆盖了2次以上！，最后当cover=0，那么说明这个区间没有整体被覆盖过，那么inlenths等于左右子区间的inlenths的长度！最后结束这次的遍历。如果没有到达更新区间，那么就分三种情况，在左子树，右子树，左右子树混合的情况，分别考虑，然后每次都会往上更新lenth和inlenths的值！

源程序代码+部分注释：

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define esp (1e-8)
using namespace std;
double x_1,y_1,x_2,y_2,ym[30000],sum;
int i,j,n,cas;
struct tree{
	double lf,rf,lenth,inlenths;
	int cover;
}s[80000];
//这里数组开的小了当初，WA了好多次
//所以一气之下开的很大！
struct node{
	double x,y1,y2;
	int flag;
}t[30000];

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

void inlen(int num){
	if(s[num].cover>1)//表示整个区间被覆盖次数大于等于2
		s[num].inlenths=s[num].rf-s[num].lf;
	else if(s[num].cover==1)
		s[num].inlenths=s[num+num].lenth+s[num+num+1].lenth;
                //整个区间只被覆盖一次，如果子区间有被覆盖大于等于1次，说明该子段的长度，
                //为被覆盖至少2次的长度
	else
		s[num].inlenths=s[num+num].inlenths+s[num+num+1].inlenths;
                //整个区间都没被覆盖，该区间覆盖2次以上的长度就等于
                //他左右子树被覆盖的长度的和
}

int cmp1(double a,double b){
	return a<b;
}

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

int Build(int x,int y,int num){
	s[num].lf=ym[x];
	s[num].rf=ym[y];
	s[num].cover=s[num].lenth=s[num].inlenths=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(fabs(s[num].lf-n.y1)<=esp&&fabs(s[num].rf-n.y2)<=esp){
		s[num].cover+=n.flag;
		len(num);
		inlen(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 sn=n;
		sn.y2=s[num+num].rf;
		modify(num+num,sn);
		sn=n;
		sn.y1=s[num+num+1].lf;
		modify(num+num+1,sn);
	}
	len(num);
	inlen(num);
}

int main(){
	scanf("%d",&cas);
	while(cas--){	
		sum=0;
		scanf("%d",&n);
		for(i=1,j=1;i<=n;i++,j+=2){
			scanf("%lf %lf %lf %lf", &x_1, &y_1, &x_2, &y_2);
			ym[j]=y_1;
			t[j].x=x_1;
			t[j].y1=y_1;
			t[j].y2=y_2;
			t[j].flag=1;
			ym[j+1]=y_2;
			t[j+1].x=x_2;
			t[j+1].y1=y_1;
			t[j+1].y2=y_2;
			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]);
		for(i=2;i<j;i++){
			sum+=s[1].inlenths*(t[i].x-t[i-1].x);
			modify(1,t[i]);
		}
		printf("%.2lf\n",sum);
              //在我的编译器上好像样例的答案为7.62但是可以过
              //我不知道有没有更好的办法能够四舍五入保留两位小数
	}
	return 0;

}