第11届浙江大学校赛比赛点评beta » ZOJ3477

ZOJ3477
ZOJ3477.cpp


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

using namespace std;

inline bool odd(int x) {
	return x % 2 != 0;
}

struct Rect {
	bool _valid;
	int a1, a2, b1, b2;

	Rect(int x, int y, int z) : _valid(true) {
		a1 = x + y - z;
		a2 = x + y + z;
		b1 = x - y - z;
		b2 = x - y + z;
		valid();
	}

	bool valid() {
		for (bool loop = true; loop && _valid; _valid &= a1 <= a2 && b1 <= b2) {
			loop = false;
			if (a1 == a2) {
			//	if (a1 % 2 != b1 % 2) {	BUG: a1 > 0 && b1 < 0 ...
				if (odd(a1) != odd(b1)) {
					++b1;
					loop = true;
				}
				if (odd(a1) != odd(b2)) {
					--b2;
					loop = true;
				}
			}
			if (b1 == b2) {
				if (odd(b1) != odd(a1)) {
					++a1;
					loop = true;
				}
				if (odd(b1) != odd(a2)) {
					--a2;
					loop = true;
				}
			}
		}
		return _valid;
	}

	bool intersect(const Rect& r) const {
		return a1 < r.a2 && r.a1 < a2 && b1 < r.b2 && r.b1 < b2;
	}

	void cut(Rect r, vector<Rect>& v) const {
		if (r.a1 <= a1) {
			v.push_back(r);
			v.back().a2 = a1;
			r.a1 = a1;
		}
		if (r.a2 >= a2) {
			v.push_back(r);
			v.back().a1 = a2;
			r.a2 = a2;
		}
		if (r.b1 <= b1) {
			v.push_back(r);
			v.back().b2 = b1;
			r.b1 = b1;
		}
		if (r.b2 >= b2) {
			v.push_back(r);
			v.back().b1 = b2;
			r.b2 = b2;
		}
	}

	void cutBy(int x1, int y1, int x2, int y2) {
		a1 = max(a1, x1 + y1);
		a2 = min(a2, x2 + y2);
		b1 = max(b1, x1 - y2);
		b2 = min(b2, x2 - y1);
	}

	void upd(pair<int, int>& p) const {
		p = min(p, make_pair((a1 + b1) / 2, (a1 - b1) / 2));
		p = min(p, make_pair((a1 + b2) / 2, (a1 - b2) / 2));
		p = min(p, make_pair((a2 + b1) / 2, (a2 - b1) / 2));
		p = min(p, make_pair((a2 + b2) / 2, (a2 - b2) / 2));
	}
};

const int MAXN = 256;
int x[MAXN], y[MAXN], z[MAXN];

void gao(int r, int c, int n, int d, vector<Rect>& ret, bool debug = false) {
	ret.clear();
	ret.push_back(Rect(1, 1, r + c));

	for (int i = 0; i < n; ++i) {
		if (z[i] > d) {
			continue;
		}
		Rect tmp(x[i], y[i], d - z[i]);
		vector<Rect> swp;
		for (vector<Rect>::const_iterator it = ret.begin(); it != ret.end(); ++it) {
			if (tmp.intersect(*it)) {
				tmp.cut(*it, swp);
			} else {
				swp.push_back(*it);
			}
		}
		ret.clear();
		for (vector<Rect>::iterator it = swp.begin(); it != swp.end(); ++it) {
			if (it->valid()) {
				ret.push_back(*it);
			}
		}
	}

	vector<Rect> swp;
	for (vector<Rect>::const_iterator it = ret.begin(); it != ret.end(); ++it) {
		it->cut(*it, swp);
	}
	ret.clear();
	for (vector<Rect>::iterator it = swp.begin(); it != swp.end(); ++it) {
		if (!it->valid()) {
		} else if (it->a1 == it->a2) {
			it->cutBy(max(1, it->a1 - c), max(1, it->a1 - r),
				min(r, it->a1 - 1), min(c, it->a1 - 1));
		} else if (it->b1 == it->b2) {
			it->cutBy(max(1, 1 + it->b1), max(1, 1 - it->b1),
				min(r, c + it->b1), min(c, r - it->b1));
		} else {
			throw 1;
		}
		if (it->valid()) {
			ret.push_back(*it);
		}
	}
}

int main() {
	char ch;
	vector<Rect> v;
	pair<int, int> p;
	int re, r, c, n, lo, up, mi, diff;

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		assert(scanf("%d%d%d%c", &r, &c, &n, &ch) == 4 && ch == '\n');
		assert(1 <= r && r <= (1 << 20) && 1 <= c && c <= (1 << 19) && 1 <= n && n <= 218);
		for (int i = 0; i < n; ++i) {
			assert(scanf("%d%d%d%c", &x[i], &y[i], &z[i], &ch) == 4 && ch == '\n');
		}
		assert(scanf("%c", &ch) == 1 && ch == '\n');
		diff = *min_element(z, z + n);
		for (int i = 0; i < n; ++i) {
			z[i] -= diff;
		}

		lo = 0;
		up = r + c + 100;
		while (lo < up) {
			mi = (lo + up) / 2;
			gao(r, c, n, mi, v);
			if (!v.empty()) {
				lo = mi + 1;
			} else {
				up = mi;
			}
		}
		assert(up < r + c);

		--up;
		printf("%d ", diff + up);
		if (up == 0) {
			printf("(%d, %d)\n", 1, 1);
		} else {
			gao(r, c, n, up, v, true);
			p = make_pair(r, c);
			for (vector<Rect>::const_iterator it = v.begin(); it != v.end(); ++it) {
				it->upd(p);
			}
			printf("(%d, %d)\n", p.first, p.second);
		}
	}
	assert(scanf("%c", &ch) == EOF);

	return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//210 	2011-04-03 01:06:35 	Accepted 	A 	C++ 	1920 	180 	watashi 	Source
Leave a Reply