Pagini recente » Cod sursa (job #1031634) | Cod sursa (job #1540793) | Cod sursa (job #2217285) | Cod sursa (job #574130) | Cod sursa (job #525)
Cod sursa(job #525)
#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;
}