Andrew Stankevich’s Contest #9解题报告 » ZOJ2696

ZOJ2696
ZOJ2696.cpp


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

using namespace std;

typedef pair<int, int> PII;
typedef pair<PII, PII> PPP;
typedef vector<PII> VPII;

inline int sign(int x) {
	return x > 0 ? 1 : x < 0 ? -1 : 0;
}

int intersection(PII a, PII b, PII c, PII d) {
	if (a.first != b.first) {
		swap(a.first, a.second);
		swap(b.first, b.second);
		swap(c.first, c.second);
		swap(d.first, d.second);
	}
	if (a.second > b.second) {
		a.second = -a.second;
		b.second = -b.second;
		c.second = -c.second;
		d.second = -d.second;
	}
	if (c > d) {
		swap(c, d);
	}
	int ret;
	if (c.first > a.first || d.first < a.first) {
		ret = -1;
	} else if (min(c.second, d.second) > b.second || max(c.second, d.second) < a.second) {
		ret = -1;
	} else if (c.first == d.first) {
		ret = max(a.second, min(c.second, d.second)) - a.second;
	} else {
		ret = c.second - a.second;
	}
	//printf("(%d,%d)-(%d,%d) (%d,%d)-(%d,%d) @%d\n", a.first, a.second, b.first, b.second,
	//	c.first, c.second, d.first, d.second, ret);
	return ret;
}

bool sameside(PII a, PII b, PII c, PII d) {
	if (a.first != b.first) {
		swap(a.first, a.second);
		swap(b.first, b.second);
		swap(c.first, c.second);
		swap(d.first, d.second);
	}
	return ((c.first < a.first) ^ (d.first < a.first)) == 0;
}

PII point(const PII& a, const PII& b, int p) {
	int dx = sign(b.first - a.first);
	int dy = sign(b.second - a.second);
	return make_pair(a.first + p * dx, a.second + p * dy);
}

VPII path(const PII& a, const PII& b, const VPII& w, int u) {
	int i, t, k = 1, p = -1;
	VPII ret;
	// printf("[path] w.size() = %d\n", (int)w.size());
	for (i = 1; i < (int)w.size(); ++i) {
		t = intersection(a, b, w[i - 1], w[i]);
		if (t != -1 && (p == -1 || p > t)) {
			p = t;
			k = i;
		}
	}
	if (p != -1) {
		ret.push_back(point(a, b, p - u));
		if ((w[k - 1].first == w[k].first && w[k].first == ret.back().first) ||
			(w[k - 1].second == w[k].second && w[k].second == ret.back().second)) {
			++k;
		}
		// printf("k = %d\n", k);
		for (i = k ; i < (int)w.size(); ++i) {
			ret.push_back(ret.back());
			if (i + 1 < (int)w.size() && sameside(w[i - 1], w[i], ret.back(), w[i + 1])) {
				if (w[i - 1].first == w[i].first) {
					ret.back().second = w[i].second - sign(w[i].second - w[i - 1].second) * u;
				} else {
					ret.back().first = w[i].first - sign(w[i].first - w[i - 1].first) * u;
				}
			} else {
				if (w[i - 1].first == w[i].first) {
					ret.back().second = w[i].second + sign(w[i].second - w[i - 1].second) * u;
				} else {
					ret.back().first = w[i].first + sign(w[i].first - w[i - 1].first) * u;
				}
			}
		}
	}
	return ret;
}

VPII trim(const VPII& v) {
	VPII ret;
	for (int i = 0; i < (int)v.size(); ++i) {
		if (ret.size() > 1) {
			if (ret.back().first == v[i].first && ret.back().first == (ret.end() - 2)->first) {
				ret.pop_back();
			} else if (ret.back().second == v[i].second && ret.back().second == (ret.end() - 2)->second) {
				ret.pop_back();
			}
		}
		if (ret.empty() || v[i] != ret.back()) {
			ret.push_back(v[i]);
		}
	}
	return ret;
}

VPII gao(const VPII& v, const VPII& w, int u) {
	int i, j;
	VPII p, q, r;
	for (i = 1; i < (int)v.size() && p.empty(); ++i) {
	//	printf("i = %d\n", i);
		p = path(v[i - 1], v[i], w, u);
	}
	if (p.empty()) {
		return v;
	}
	for (j = (int)v.size() - 2; j >= 0 && q.empty(); --j) {
	//	printf("j = %d\n", j);
		q = path(v[j + 1], v[j], w, u);
	}
	--i;
	++j;
	// printf("i = %d; j = %d\n", i, j);
	r.insert(r.end(), v.begin(), v.begin() + i);
	r.insert(r.end(), p.begin(), p.end());
	r.insert(r.end(), q.rbegin(), q.rend());
	r.insert(r.end(), v.begin() + j + 1, v.end());
	return trim(r);
}

void output(int a, int b) {
	while (a % 2 == 0 && b % 2 == 0) {
		a /= 2;
		b /= 2;
	}
	printf("%d/%d", a, b);
}

int main() {
	int n, m, u, p[16];
	VPII v[16];

	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; ++i) {
			scanf("%d", &p[i]);
			--p[i];
		}
		m = 1 << (2 * n);	// if m = 1 << n then WA
		for (int i = 0; i < n; ++i) {
			u = 1 << (2 * (n - 1 - i));
			v[i].clear();
			v[i].push_back(make_pair(i * m, 0));
			if (i != p[i]) {
				v[i].push_back(make_pair(i * m, m / 2));
				v[i].push_back(make_pair(p[i] * m, m / 2));
			}
			v[i].push_back(make_pair(p[i] * m, m));
			for (int j = 0; j < i; ++j) {
				v[i] = gao(v[i], v[j], u);
			}
		}

		for (int i = 0; i < n; ++i) {
			printf("%d\n", (int)v[i].size() - 1);
			for (int j = 0; j < (int)v[i].size(); ++j) {
				output(v[i][j].first, m);
				putchar(' ');
				output(v[i][j].second, m);
				putchar('\n');
			}
		}
		puts("");
	}

	return 0;
}
Leave a Reply