1909.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1909 on 2005-11-01 at 00:55:38 */ 
#include <cstdio>
#include <cstdlib>

const int MAX = 20480;
const int N_MAX = 10240;
const int LIMIT = 10000;

class Line {
public:
	int l;
	int r;
	int p;
	bool enter;
	void init(int la, int ra, int pa, int e) {
		l = la;
		r = ra;
		p = pa;
		enter = e;
	}
};

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

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

int main()
{
	LineTree tree(0, MAX);
	Line line[2][N_MAX];
	int n, m, i, j;
	int x1, y1, x2, y2, p;
	int total;

	while(scanf("%d", &n) == 1) {
		for(i = 0; i < n; i++) {
			scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
			x1 += LIMIT;
			x2 += LIMIT;
			y1 += LIMIT;
			y2 += LIMIT;
			line[0][2*i].init(y1, y2, x1, true);
			line[0][2*i+1].init(y1, y2, x2, false);
			line[1][2*i].init(x1, x2, y1, true);
			line[1][2*i+1].init(x1, x2, y2, false);
		}
		m = 2 * n;
		total = 0;
		for(i = 0; i < 2; i++) {
			qsort(line[i], m, sizeof(Line), cmp);
			p = 0;
			tree.init();
			for(j = 0; j < m; j++) {
				if(line[i][j].enter) {
					tree.insert(line[i][j].l, line[i][j].r);
				} else {
					tree.del(line[i][j].l, line[i][j].r);
				}
				total += iabs(tree.coverLen - p);
				p = tree.coverLen;
			}
		}
		printf("%d\n", total);
	}
	
	return 0;
}

int cmp(const void *a, const void *b)
{
	Line *x = (Line*)a, *y = (Line*)b;
	
	if(x->p < y->p) {
		return -1;
	} else if(x->p > y->p) {
		return 1;
	} else {
		if(y->enter) {
			return 1;
		} else {
			return -1;
		}
	}
}
inline int iabs(int a)
{
	return a > 0 ? a : -a;
}