Cod sursa(job #212770)

Utilizator tvladTataranu Vlad tvlad Data 6 octombrie 2008 19:50:24
Problema Overlap Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <map>
using namespace std;

const int N = 800;

struct punct { int x,y; };
bool operator< ( const punct &a, const punct &b ) { return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x); }

int n;
punct v[N], vr[N];
map<punct,int> pMap, tempMap;
int used[N];

punct rot ( punct a, int r ) {
	punct b;
	if (r == 0) {
		b.x = a.x;
		b.y = a.y;
	} else
	if (r == 1) {
		b.x = a.y;
		b.y = -a.x;
	} else
	if (r == 2) {
		b.x = -a.x;
		b.y = -a.y;
	} else {
		b.x = -a.y;
		b.y = a.x;
	}
	return b;
}

int main() {
	freopen("overlap.in","rt",stdin);
	freopen("overlap.out","wt",stdout);
	scanf("%d",&n);
	for (int i = 0; i < n; ++i) {
		scanf("%d %d",&v[i].x,&v[i].y);
		pMap[v[i]] = i;
	}
	for (int r = 0; r < 4; ++r) {
		for (int i = 0; i < n; ++i) vr[i] = rot(v[i],r);
		tempMap.clear();
		for (map<punct,int>::iterator it = pMap.begin(); it != pMap.end(); ++it) tempMap[it->first] = it->second;
		punct move, nou;
		for (int p0 = 1; p0 < n; ++p0) {
			for (int i = 1; i < n; ++i) used[i] = 0;
			used[0] = 1;
			used[p0] = 2;
			move.x = v[p0].x - vr[0].x;
			move.y = v[p0].y - vr[0].y;
			for (int i = 1; i < n; ++i) {
				if (!used[i]) {
					nou.x = vr[i].x + move.x;
					nou.y = vr[i].y + move.y;
					map<punct,int>::iterator it = tempMap.find(nou);
					if (it != tempMap.end()) {
						used[i] = 1;
						used[it->second] = 2;
						tempMap.erase(it);
					}
				}
			}
			bool ok = true;
			for (int i = 0; i < n; ++i)
				if (!used[i])
					ok = false;
			if (ok) {
				for (int i = 0; i < n; ++i) printf("%d\n",used[i]);
				return 0;
			}
		}
	}
	return 0;
}