atlantis(线段树求矩形并).cpp

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

//对Y轴就行离散化，用线段树维护
//对Y轴排序后，依据下标构造线段树
//Accepted 244K 15MS G++ 
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct node {
	double l, r;
	node * pl, * pr;
	double len;//测度
	int il,ir;
	int ls;//覆盖
}mem[300000];
int mem_pos;

struct node2 {
	double x,y1,y2;
	int flag;
	bool operator < (const node2 & tt) const {
		return x < tt.x;
	}
}line[2100];
int ls;

double y[210];

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 ->ls > 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
make_tree(node * & root, int il, int ir) 
{
	int mid = (il+ir)/2;
	
	if(root == NULL) {
		root = new_node();
		root ->il = il;
		root ->ir = ir;
		root ->l = y[il];
		root ->r = y[ir];
	}
	if(ir - il > 1) {
		make_tree(root ->pl, il, mid);
		make_tree(root ->pr, mid, ir);
	}
}

void 
update(node * root, node2 edge)
{
	if(root ->l == edge.y1 && root ->r == edge.y2) {
		root ->ls += edge.flag;//矩形进入或退出
		cal_len(root);
		return;
	}

	if(root ->pl ->r > edge.y1) {
		if(root ->pl ->r >= edge.y2) {
			update(root ->pl, edge);
		}
		else {
			node2 edge2 = edge;
			edge2.y2 = root ->pl ->r;
			update(root ->pl, edge2);
			edge2 = edge;
			edge2.y1 = root ->pr ->l;
			update(root ->pr, edge2);
		}
	}
	else {
		update(root ->pr, edge);
	}
	cal_len(root);
}


int main()
{
	node * root;
	int t,n,i,j;
	double x1,y1,x2,y2,size;
	t = 1;
	while(scanf("%d", &n), n) {
		ls = mem_pos = 0;
		
		for(i=0;i<n;i++) {
			scanf("%lf %lf %lf %lf", &x1,&y1,&x2,&y2);
			line[ls].x = x1;
			line[ls+1].x = x2;
			line[ls].y1 = y1;	line[ls].y2 = y2;
			line[ls+1].y1 = y1;	line[ls+1].y2 = y2;
			line[ls].flag = 1;
			line[ls+1].flag = -1;
			y[ls] = y1;
			y[ls+1] = y2;
			ls += 2;
		}
		sort(line, line+ls);
		sort(y,y+ls);

		root = NULL;
		make_tree(root, 0, ls-1);

		size = 0;
		update(root, line[0]);
		for(i=1;i<ls;i++) {
			size += root ->len * (line[i].x - line[i-1].x);
			update(root, line[i]);
		}
		printf("Test case #%d\nTotal explored area: %.2lf\n\n", t ++, size);
	}
}