1396.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1396 on 2006-01-16 at 18:34:11 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 48000;

class Point {
public:
	int x, y, o;
	bool enter, pour;
	void init(int, int, int, bool, bool);
	bool operator <(const Point&) const;
};
void Point::init(int cx, int cy, int co = -1, bool en = false, bool pu = false) {
	x = cx; y = cy; o = co; enter = en; pour = pu;
}
bool Point::operator <(const Point& p) const {
	if(x != p.x) return x < p.x;
	else if(enter != p.enter) return enter;
	else if(enter) return y < p.y;
	else return y > p.y;
}

class Roof {
private:
	Point begin, end;
public:
	void init(int, int, int, int);
	double height(int);
};
void Roof::init(int bx, int by, int ex, int ey) {
	begin.init(bx, by); end.init(ex, ey);
}
double Roof::height(int x) {
	double k = (double)(x-begin.x)*(end.y-begin.y)/(end.x-begin.x);
	return (k + begin.y);
}

class List {
public:
	int next[MAX], prev[MAX];
	int in[MAX], pour[MAX];
	void init(int);
	void insertBack(int, int);
	void insertBefore(int, int);
	void del(int);
	void link(int);
};
void List::init(int n) {
	int i;
	for(i = 0; i < n; i++) {
		pour[i] = next[i] = prev[i] = -1;
		in[i] = 0;
	}
}
void List::insertBack(int n, int m) {
	if(next[n] != -1) prev[next[n]] = m, next[m] = next[n];
	prev[m] = n; next[n] = m;
}
void List::insertBefore(int n, int m) {
	if(prev[n] != -1) next[prev[n]] = m, prev[m] = prev[n];
	next[m] = n; prev[n] = m;
}
void List::del(int n) {
	if(prev[n] != -1) next[prev[n]] = next[n];
	if(next[n] != -1) prev[next[n]] = prev[n];
}
void List::link(int n) {
	if(next[n] != -1) in[next[n]]++, pour[n] = next[n];
}

Point point[MAX*2];
Roof roof[MAX];
List list;

int main()
{
	int i, n, t, T;
	int stack[MAX];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		int m = 2 * n;
		for(i = 0; i < n; i++) {
			int bx, by, ex, ey;
			scanf("%d %d %d %d", &bx, &by, &ex, &ey);
			bool left = (by < ey);
			point[2*i].init(bx, by, i, true, left);
			point[2*i+1].init(ex, ey, i, false, !left);
			roof[i].init(bx, by, ex, ey);
		}
		sort(point, point+m);
		list.init(n);
		int rain[MAX] = { 0 }, top = -1;
		for(i = 0; i < m; i++) {
			if(top != -1) rain[top] += point[i].x - point[i-1].x;
			if(point[i].enter) {
				if(top == -1) top = point[i].o;
				else {
					int p = top;
					while(p != -1 && (double)point[i].y < roof[p].height(point[i].x)) {
						if(list.next[p] == -1) {
							list.insertBack(p, point[i].o);
							p = -1;
							break;
						} else p = list.next[p];
					}
					if(p != -1) {
						if(p == top) top = point[i].o;
						list.insertBefore(p, point[i].o);
					}
				}
			} else {
				if(point[i].o == top) top = list.next[top];
				list.del(point[i].o);
			}
			if(point[i].pour) list.link(point[i].o);
		}
		top = 0;
		for(i = 0; i < n; i++) {
			if(list.in[i] == 0) stack[top++] = i;
		}
		while(top > 0) {
			int p = stack[--top];
			if(list.pour[p] != -1) {
				list.in[list.pour[p]]--;
				rain[list.pour[p]] += rain[p];
				if(list.in[list.pour[p]] == 0) stack[top++] = list.pour[p];
			}
		}
		for(i = 0; i < n; i++) printf("%d\n", rain[i]);
	}
	
	return 0;
}