Cod sursa(job #667)

Utilizator wefgefAndrei Grigorean wefgef Data 11 decembrie 2006 18:18:32
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;

#define x first
#define y second
#define mp(a, b) make_pair(a, b)

#define Nmax 1024

pair<int, int> v[Nmax], u[Nmax];
int n, af[Nmax], sx, sy, poz[Nmax], loc[Nmax], par[Nmax], viz[Nmax], sol, nr, mark[Nmax];

void readdata()
{
	freopen("overlap.in", "r", stdin);
	freopen("overlap.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d %d", &v[i].x, &v[i].y);
}

int cauta(pair<int, int> p)
{
	int st, dr, m;
	st = 0; dr = n-1;
	while (st < dr)
	{
		m = (st+dr)/2;
		if (v[m] == p) return m;
		if (v[m] < p) st = m+1;
		else dr = m-1;
	}
	if (st == dr)
	if (v[st] == p) return st;
	return -1;
}

void qsort(int st, int dr)
{
	pair<int, int> sch, aux;
	int i, j, aux2;
	
	i = st; j = dr;
	sch = v[(st+dr)/2];
	do
	{
		while (v[i] < sch) ++i;
		while (v[j] > sch) --j;
		if (i <= j)
		{
			aux = v[i]; v[i] = v[j]; v[j] = aux;
			aux2 = poz[i]; poz[i] = poz[j]; poz[j] = aux2;
			++i; --j;
		}
	}
	while (i <= j);
	if (i < dr) qsort(i, dr);
	if (j > st) qsort(st, j);
}

void df(int k)
{
	++nr;
	viz[k] = 1;
	if (par[k] != -1)
	if (!viz[par[k]])
	{
		af[par[k]] = 1-af[k];
		df(par[k]);
	}
}

void solve()
{
	int k, i, j;
	
	for (i = 0; i < n; ++i)
		poz[i] = i;
	qsort(0, n-1);
	for (i = 0; i < n; ++i) loc[poz[i]] = i;
	
	for (k = 0; k < 4; ++k)
	{
		for (i = 0; i < n; ++i)
		switch(k)
		{
			case 0 : u[i] = v[i]; break;
			case 1 : u[i].x = v[i].y; u[i].y = -v[i].x; break;
			case 2 : u[i].x = -v[i].x; u[i].y = -v[i].y; break;
			case 3 : u[i].x = -v[i].y; u[i].y = v[i].x;			
		}
		for (i = 1; i < n; ++i)
		{
			memset(par, -1, sizeof(par));
			memset(mark, 0, sizeof(mark));
			sx = v[i].x - u[0].x;
			sy = v[i].y - u[0].y;

			for (j = 0; j < n; ++j)
			{
				par[j] = cauta( mp(u[j].x+sx, u[j].y+sy) );
				if (par[j] > -1) mark[par[j]] = 1;
			}
			
			memset(viz, 0, sizeof(viz));
			sol = 1;
			for (j = 0; j < n; ++j)
				if (!mark[j]) 
				{
					nr = 0;
					af[j] = 1;
					df(j);
					if (nr % 2 == 1) sol = 0;
				}
			for (j = 0; j < n; ++j)
				if (!viz[j])
				{
					nr = 0;
					af[j] = 1;
					df(j);
					if (nr % 2 == 1) sol = 0;
				}
			if (sol)
			{
				for (i = 0; i < n; ++i)
					printf("%d\n", 1+af[loc[i]]);
				return;
			}
		}
	}
}

int main()
{
	readdata();
	solve();
	return 0;
}