1860.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1860 on 2005-10-31 at 21:01:36 */ 
#include <cstdio>
#include <cstdlib>

const int MAX = 32768;

class VertLine {
public:
	int u;
	int d;
	long long x;
	bool enter;
	void init(long long xa, int up, int down, bool e) {
		x = xa;
		u = up;
		d = down;
		enter = e;
	}
};

class LineTree {
private:
	LineTree *left;
	LineTree *right;
	int cover;
	int x;
	int y;
	void updateLen() {
		if(cover > 0) {
			covLen = y - x;
		} else if(y - x == 1) {
			covLen = 0;
		} else {
			covLen = left->covLen + right->covLen;
		}
	}
public:
	long long covLen;
	LineTree(int l, int r) {
		x = l;
		y = r;
		if(y != x + 1) {
			int m = (x + y) / 2;
			left = new LineTree(x, m);
			right = new LineTree(m, y);
		} else {
			left = NULL;
			right = NULL;
		}
	}
	void init() {
		if(left != NULL) {
			left->init();
		}
		covLen = 0;
		cover = 0;
		if(right != NULL) {
			right->init();
		}
	}
	void insert(int l, int r) {
		if(l <= x && y <= r) {
			cover++;
		} else {
			if(l < (x + y) / 2) {
				left->insert(l, r);
			}
			if(r > (x + y) / 2) {
				right->insert(l, r);
			}
		}
		updateLen();
	}
	void del(int l, int r) {
		if(l <= x && y <= r) {
			cover--;
		} else {
			if(l < (x + y) / 2) {
				left->del(l, r);
			}
			if(r > (x + y) / 2) {
				right->del(l, r);
			}
		}
		updateLen();
	}
};

int cmp(const void*, const void*);

int main()
{
	LineTree yTree(0, MAX);
	VertLine vl[2*MAX];
	long long x1, y1, x2, y2;
	int i, m, n;
	long long area;
	
	while(scanf("%d", &n) == 1) {
		yTree.init();
		for(i = 0; i < n; i++) {
			scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
			vl[2*i].init(x1, y2, y1, true);
			vl[2*i+1].init(x2, y2, y1, false);
		}
		m = 2 * n;
		qsort(vl, m, sizeof(VertLine), cmp);
		area = 0;
		yTree.insert(vl[0].d, vl[0].u);
		for(i = 1; i < m; i++) {
			area += (vl[i].x - vl[i-1].x) * yTree.covLen;
			if(vl[i].enter) {
				yTree.insert(vl[i].d, vl[i].u);
			} else {
				yTree.del(vl[i].d, vl[i].u);
			}
		}
		printf("%lld\n", area);
	}
	
	return 0;
}

int cmp(const void *a, const void *b)
{
	VertLine *x = (VertLine*)a, *y = (VertLine*)b;
	if(x->x < y->x) {
		return -1;
	} else {
		return 1;
	}
}