Cod sursa(job #525)

Utilizator wefgefAndrei Grigorean wefgef Data 11 decembrie 2006 14:27:32
Problema Overlap Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 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, rez[Nmax], sx, sy, poz[Nmax], loc[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 (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 solve()
{
	int k, i, sol, j, pos;
	
	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 = 1; i < n; ++i)
	{
		memset(rez, 0, sizeof(rez));
		switch(k)
		{
			case 0 : u[0] = v[0]; break;
			case 1 : u[0].x = v[0].y; u[0].y = -v[0].x; break;
			case 2 : u[0].x = -v[0].x; u[0].y = -v[0].y; break;
			case 3 : u[0].x = -v[0].y; u[0].y = v[0].x;
		}
		rez[0] = 1; rez[i] = 2;
		sx = v[i].x - u[0].x;
		sy = v[i].y - u[0].y;
		sol = 1;
		for (j = 0; j < n; ++j)
		if (rez[j] == 0)
		{
			rez[j] = 1;
			switch(k)
			{
				case 0 : u[j] = v[j]; break;
				case 1 : u[j].x = v[j].y; u[j].y = -v[j].x; break;
				case 2 : u[j].x = -v[j].x; u[j].y = -v[j].y; break;
				case 3 : u[j].x = -v[j].y; u[j].y = v[j].x;
			}
			pos = cauta( mp(u[j].x+sx, u[j].y+sy) );
			if (pos == -1) { sol = 0; break; }
			rez[pos] = 2;
		}	
		if (sol)
		{
			for (j = 0; j < n; ++j)
				printf("%d\n", rez[loc[j]]);
			return;
		}
	}
}

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