狗狗40题搞完纪念 » 1029

1029
1029.cpp


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

using namespace std;

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

void uniform(VPII& v) {
	int x = v.front().first;
	int y = v.front().second;
	for (VPII::const_iterator i = v.begin(); i != v.end(); ++i) {
		x = min(x, i->first);
		y = min(y, i->second);
	}
	for (VPII::iterator i = v.begin(); i != v.end(); ++i) {
		i->first -= x;
		i->second -= y;
	}
	sort(v.begin(), v.end());
}

VPII _minpres3(VPII v) {
	VPII ret(v);
	for (VPII::iterator i = v.begin(); i != v.end(); ++i) {
		swap(i->first, i->second);
	}
	uniform(v);
	ret = min(ret, v);
	return ret;
}

VPII _minpres2(VPII v) {
	VPII ret(_minpres3(v));
	for (VPII::iterator i = v.begin(); i != v.end(); ++i) {
		i->second = -i->second;
	}
	uniform(v);
	ret = min(ret, _minpres3(v));
	return ret;
}

VPII _minpres1(VPII v) {
	VPII ret(_minpres2(v));
	for (VPII::iterator i = v.begin(); i != v.end(); ++i) {
		i->first = -i->first;
	}
	uniform(v);
	ret = min(ret, _minpres2(v));
	return ret;
}

void minpres(VPII& v) {
	uniform(v);
	v = _minpres1(v);
}

const int MAXN = 128;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
/*
void dump(int x) {
	printf("%d", x);
}

template<typename T, typename S>
void dump(const pair<T, S>& p) {
	printf("(");
	dump(p.first);
	printf(", ");
	dump(p.second);
	printf(")");
}

template<typename T>
void dump(const vector<T>& v) {
	printf("{");
	for (typename vector<T>::const_iterator i = v.begin(); i != v.end(); ++i) {
		dump(*i);
		printf(", ");
	}
	puts("}");
}
*/
void gao(int r, int c, int n, VVPII& ret) {
	static int x, y, p;
	static bool a[MAXN][MAXN];

	memset(a, 0, sizeof(a));
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &x, &y);
		a[x + 1][y + 1] = true;
	}

	ret.clear();
	for (int i = 1; i <= r; ++i) {
		for (int j = 1; j <= c; ++j) {
			if (!a[i][j]) {
				continue;
			}
			ret.push_back(VPII());
			a[i][j] = false;
			ret.back().push_back(make_pair(i, j));
			p = 0;
			while (p < (int)ret.back().size()) {
				x = ret.back()[p].first;
				y = ret.back()[p].second;
				++p;
				for (int k = 0; k < 4; ++k) {
					if (a[x + dx[k]][y + dy[k]]) {
						a[x + dx[k]][y + dy[k]] = false;
						ret.back().push_back(make_pair(x + dx[k], y + dy[k]));
					}
				}
			}
			minpres(ret.back());
		}
	}
	sort(ret.begin(), ret.end());
//	dump(ret);
}

int main() {
	int re, r, c, n;
	VVPII a, b;

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		scanf("%d%d%d", &r, &c, &n);
		gao(r, c, n, a);
		gao(r, c, n, b);
		puts(a == b ? "YES" : "NO");
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//362 	2010-07-05 19:32:04 	Accepted 	1029 	C++ 	10 	196 	anotherpeg 	Source
Leave a Reply