Cod sursa(job #726423)

Utilizator danalex97Dan H Alexandru danalex97 Data 27 martie 2012 11:03:36
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define Nmax 810

int n, i, j, k, ShX, ShY, p, q, poz, ok, par;
struct punct{ int x; int y; } a[Nmax], init[Nmax];
int fol[Nmax], v[Nmax], sol[Nmax], afis[Nmax];

inline int cmp(punct a, punct b) 
{
	if (a.x != b.x) return a.x < b.x;
	else return a.y < b.y;
}

void cit() 
{
	freopen("overlap.in", "r", stdin);
	freopen("overlap.out", "w", stdout);
	
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d %d", &a[i].x, &a[i].y);
		init[i] = a[i];
	}
	
	sort(a + 1, a + n + 1, cmp);
}

void rotesc(int k) 
{
	if (k == 0) return;
	if (k != 0) 
	{
		int x = p, y = q;
		
		if (k == 1) {p = y; q = -x;}
		if (k == 2) {p = -x; q = -y;}
		if (k == 3) {p = -y; q = x;}
	}
}

int caut(int p, int q) 
{
	int st = 0, dr = n + 1, r = 0;
	while (st + 1 < dr)
	{
		r = (st + dr) / 2;
		
		if (a[r].x > p) dr = r;
		else if (a[r].x < p) st = r;
			 else if (a[r].x == p) 
			 {
					if (a[r].y > q) dr = r;
					else if (a[r].y < q) st = r;
					     else if (fol[r] == 0) return r;
					          else return -1;
				  }
	}
	return -1;
}

int verif_ok() 
{
	ok = 1;
	for (int i = 1; i <= n; i++)
		if (fol[i] == 0) ok = 0;
		else fol[i] = 0;
	fol[0] = 1;
	for (int i = 1; i <= n; i++)
		if (fol[i] == 0 && v[i] != 0) 
		{
			j = i; par = 0;
			while (fol[j] == 0) 
			{
				par++; fol[j] = 1;
				sol[j] = par % 2 + 1;
				j = v[j];
			}
			if (par % 2 == 1) ok = 0;
		}
	
	return ok;
}

void solve() 
{
	for (k = 0; k <= 4; k++) 
	{
		for (i = 2; i <= n; i++)
		{
			p = a[1].x; q = a[1].y;
			rotesc(k);		
	
			for (j = 0; j <= n; j++) v[j] = fol[j] = 0;
			fol[1] = 1;	v[1] = i;
			
			fol[i] = 1;
			ShX = a[i].x - p;
			ShY = a[i].y - q;
			
			for (j = 2; j <= n; j++)
				if (fol[j] == 0) 
				{
					p = a[j].x; q = a[j].y;
					rotesc(k);
					
					p = p + ShX;
					q = q + ShY;
					
					poz = caut(p, q);
					if (poz > 0) 
					{
						fol[poz] = fol[j] = 1;
						v[j] = poz;
					}
				}
			
			if (verif_ok()) return;
		}
	}
}

void write() 
{
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (init[j].x == a[i].x && init[j].y == a[i].y) 
				afis[j] = sol[i];
	for (i = 1; i <= n; i++)
		printf("%d\n", afis[i]);
}

int main() 
{
	
	cit();
	solve();
	write();
	
	return 0;
}