Andrew Stankevich’s Contest #11解题报告 » ZOJ3372

ZOJ3372
ZOJ3372.cpp


#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

const int MAXN = 128;

struct Rectangle {
	int x1, y1, x2, y2;
} rect[MAXN];

int common(int x1, int x2, int y1, int y2) {
	return x1 == x2 ? max(0, y2 - y1) : 0;
}

int common(const Rectangle& lhs, const Rectangle& rhs) {
	int ret = 0;
	ret += common(lhs.x1, rhs.x2, max(lhs.y1, rhs.y1), min(lhs.y2, rhs.y2));
	ret += common(lhs.x2, rhs.x1, max(lhs.y1, rhs.y1), min(lhs.y2, rhs.y2));
	ret += common(lhs.y1, rhs.y2, max(lhs.x1, rhs.x1), min(lhs.x2, rhs.x2));
	ret += common(lhs.y2, rhs.y1, max(lhs.x1, rhs.x1), min(lhs.x2, rhs.x2));
	return ret;
}

int main() {
	int n, p, c, l[MAXN], f[MAXN], x[MAXN];
	double s, t, v[MAXN];
	vector<pair<int, int> > e[MAXN];

	while (scanf("%d%d%d%d%lf", &n, &rect[0].x2, &rect[0].y2, &p, &s) != EOF) {
		rect[0].x1 = rect[0].y1 = 0;
		for (int i = 1; i <= n; ++i) {
			scanf("%d%d%d%d%lf", &rect[i].x1, &rect[i].y1, &rect[i].x2, &rect[i].y2, &v[i]);
			l[i] = 2 * (rect[i].x2 - rect[i].x1 + rect[i].y2 - rect[i].y1);
			v[i] *= (rect[i].x2 - rect[i].x1) * (rect[i].y2 - rect[i].y1);
			e[i].clear();
			x[i] = -1;
			f[i] = 0;
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j < i; ++j) {
				c = common(rect[i], rect[j]);
				if (c > 0) {
					e[i].push_back(make_pair(j, c));
					e[j].push_back(make_pair(i, c));
				}
			}
		}

		x[p] = 0;
		t = 0;
		c = 0;
		for (int i = 1; i <= n; ++i) {
			int k = -1;
			double dt;
			for (int j = 1; j <= n; ++j) {
				if (x[j] == 0 && (k == -1 || v[j] * c / f[j] < dt)) {
					k = j;
					dt = j == p ? v[j] : v[j] * c / f[j];
				}
			}
			x[k] = 1;
			t += dt;
			// printf("%d: %lf %d (%d %d %d %d)\n", k, t, c, f[1], f[2], f[3], f[4]);
			for (int j = 1; j <= n; ++j) {
				if (x[j] == 0) {
					v[j] -= dt * f[j] / c;
				}
			}
			c += l[k];
			c -= 2 * f[k];
			for (int j = 0; j < (int)e[k].size(); ++j) {
				if (x[e[k][j].first] != 1) {
					x[e[k][j].first] = 0;
					f[e[k][j].first] += e[k][j].second;
				}
			}
		}

		printf("%.8lf\n", t / s * 10);
	}

	return 0;
}
// Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
// 513 	2010-07-08 14:18:44 	Accepted 	asc11k 	C++ 	10 	180 	anotherpeg 	Source

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//181 	2010-07-08 14:43:28 	Accepted 	asc11k 	C++ 	0 	180 	watashi@Zodiac 	Source
Leave a Reply