Pagini recente » Cod sursa (job #1681390) | Cod sursa (job #1009953) | Cod sursa (job #1060156) | Cod sursa (job #2221731) | Cod sursa (job #841844)
Cod sursa(job #841844)
#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;
}