1059.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1059 on 2006-06-06 at 19:05:10 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 2048;

int dx[MAX], dy[MAX];

class SegTree {
private:
	SegTree *left, *right;
	int x, y;
	void update();
public:
	int len; bool cover;
	SegTree(int, int);
	~SegTree();
	void clear();
	void insert(int, int);
};
SegTree::SegTree(int l, int r) : x(l), y(r) {
	if(y == x+1) left = right = NULL;
	else {
		int m = (x + y) / 2;
		left = new SegTree(x, m);
		right = new SegTree(m, y);
	}
}
SegTree::~SegTree() {
	if(left != NULL) delete left;
	if(right != NULL) delete right;
}
void SegTree::clear() {
	len = 0; cover = false;
	if(left != NULL) left->clear();
	if(right != NULL) right->clear();
}
void SegTree::update() {
	if(cover) len = dx[y]-dx[x];
	else if(y-x == 1) len = 0;
	else len = left->len + right->len;
}
void SegTree::insert(int l, int r) {
	if(cover) return;
	else if(l <= x && y <= r) cover = true;
	else if(y-x != 1) {
		if(l < (x+y)/2) left->insert(l, r);
		if(r > (x+y)/2) right->insert(l, r);
	}
	update();
}

int dispart(int*, int*, int);

int main()
{
	int w, h, n, i, j;
	int area[2520], x[MAX], y[MAX], co[MAX/2];

	while(scanf("%d %d %d", &w, &h, &n) != EOF) {
		co[0] = 1; x[0] = y[0] = 0; x[1] = w; y[1] = h;
		int lmt = 1;
		for(i = 1; i <= n; i++) {
			scanf("%d %d %d %d %d", &x[2*i], &y[2*i], &x[2*i+1], &y[2*i+1], &co[i]);
			lmt = max(co[i], lmt);
		}
		memset(area, 0, sizeof(area));
		int xn = dispart(x, dx, 2*n+2), yn = dispart(y, dy, 2*n+2);
		SegTree st(0, xn-1);
		for(i = yn-2; i >= 0; i--) {
			st.clear();
			for(j = n; j >= 0; j--) {
				if(y[2*j] > i || y[2*j+1] <= i) continue;
				int len = st.len; st.insert(x[2*j], x[2*j+1]);
				area[co[j]] += (dy[i+1]-dy[i])*(st.len-len);
			}
		}
		for(i = 1; i <= lmt; i++)
			if(area[i] != 0) printf("%d %d\n", i, area[i]);
		putchar('\n');
	}

	return 0;
}

int dispart(int* src, int* dis, int n)
{
	int i, dn = 0;
	for(i = 0; i < n; i++) dis[i] = src[i];
	sort(dis, dis+n);
	for(i = 0; i < n; i++)
		if(i == 0 || dis[i] != dis[i-1]) dis[dn++] = dis[i];
	for(i = 0; i < n; i++) src[i] = lower_bound(dis, dis+dn, src[i]) - dis;
	return dn;
}