覆盖的面积(线段树矩形交).cpp

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

//线段树维护，求矩形交
#include <cstdio>
#include <string>
#include <algorithm>
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<n;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<ls;i++) {
			intersections += root ->relen * (list[i].x - list[i-1].x);
			update(root, list[i]);
		}
		printf("%.2lf\n", intersections);
	}
}