Pagini recente » Cod sursa (job #2217145) | Cod sursa (job #534630) | Cod sursa (job #660612) | Cod sursa (job #2795512) | Cod sursa (job #667)
Cod sursa(job #667)
#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;
}