杭电acm解题报告2001---2099.

				//线段树维护，求矩形交
				#include 
				#include 
				#include 
				using namespace std;
				
				struct node {
					double l,r;
					node * pl, * pr;
					double len;//测度，求矩形并
					int cover;//完全覆盖数
					double relen;//重复测度，求矩形交
				}mem[10000];
				int mem_pos;
				
				struct line {
					double x,y1,y2;
					int flag;
					bool operator < (const line & tt ) const {
						return x < tt.x;
					}
				}list[2100];
				double yaxis[2100];
				
				node *
				new_node()
				{
					node * pt = &mem[mem_pos ++];
					memset(pt,0,sizeof(node));
					return pt;
				}
				
				void
				cal_len(node * root)
				{
					root ->len = 0;
					if(root ->cover > 0) {
						root ->len = root ->r - root ->l;
					}
					else {
						if(root ->pl) {
							root ->len += root ->pl ->len;
						}
						if(root ->pr) {
							root ->len += root ->pr ->len;
						}
					}
				}
				
				void
				cal_relen(node * root)
				{
					root ->relen = 0;
					if(root ->cover > 1) {//当本线段被完全覆盖多次
						root ->relen = root ->r - root ->l;
					}
					else if(root ->cover == 1) {//当本线段被完全覆盖一次
						if(root ->pl) {
							root ->relen += root ->pl ->len;
						}
						if(root ->pr) {
							root ->relen += root ->pr ->len;
						}
					}
					else {//未被覆盖过
						if(root ->pl) {
							root ->relen += root ->pl ->relen;
						}
						if(root ->pr) {
							root ->relen += root ->pr ->relen;
						}
					}
				}
				
				node *
				make_tree(int il, int ir)
				{
					node * root = new_node();
					root ->l = yaxis[il];
					root ->r = yaxis[ir];
					if(ir - il > 1) {
						int mid = (il+ir)/2;
						root ->pl = make_tree(il, mid);
						root ->pr = make_tree(mid, ir);
					}
					return root;
				}
				
				void
				update(node * root, line e)
				{
					if(root ->l == e.y1 && root ->r == e.y2) {//只覆盖本区间，不覆盖子区间
						root ->cover += e.flag;
						cal_len(root);
						cal_relen(root);
						return ;
					}
					if(root ->pl ->r > e.y1) {//[l,r)
						if(root ->pl ->r >= e.y2) {
							update(root ->pl, e);
						}
						else {
							line e2 = e;
							e2.y2 = root ->pl ->r;
							update(root ->pl, e2);
							e2 = e;
							e2.y1 = root ->pr ->l;
							update(root ->pr, e2);
						}
					}
					else {
						update(root ->pr, e);
					}
					cal_len(root);
					cal_relen(root);
				}
				
				int main()
				{
					int t,n,i;
					int ls;
					double x1,x2,y1,y2;
					double sum, unions, intersections;
					scanf("%d", &t);
					while(t --) {
						ls = 0;
						mem_pos = 0;
						sum = unions = intersections = 0;
						scanf("%d", &n);
						for(i=0;i							scanf("%lf %lf %lf %lf", &x1,&y1,&x2,&y2);
							list[ls].x = x1;
							list[ls].y1 = y1;	list[ls].y2 = y2;
							list[ls].flag = 1;
							list[ls+1].x = x2;
							list[ls+1].y1 = y1;	list[ls+1].y2 = y2;
							list[ls+1].flag = -1;
							yaxis[ls] = y1;
							yaxis[ls+1] = y2;
							ls += 2;
							sum += (x2 - x1)*(y2 - y1);
						}
						sort(yaxis, yaxis+ls);
						sort(list, list+ls);
						
						node * root = make_tree(0, ls-1);
						update(root, list[0]);
						for(i=1;i							intersections += root ->relen * (list[i].x - list[i-1].x);
							update(root, list[i]);
						}
						printf("%.2lf\n", intersections);
					}
				}