Pagini recente » Cod sursa (job #2292235) | Cod sursa (job #1468029) | Cod sursa (job #2552227) | Cod sursa (job #3148390) | Cod sursa (job #1755298)
#include<fstream>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
int n, i, j, ii, st, dr, mid, nod, k, sx, sy, nr, ok;
int w[805], f[805], viz[805], sol[805], sol1[805];
pair<int, int> v[805], p, vv[805];
ifstream fin("overlap.in");
ofstream fout("overlap.out");
int lg(int nod){
int nr = 0;
while(viz[nod] == 0 && nod != 0){
viz[nod] = 1;
nr++;
sol1[nod] = nr % 2 + 1;
nod = w[nod];
}
return nr;
}
pair<int, int> rotate(pair<int, int> p, int k){
pair<int, int> aux;
if(k == 1){
aux.x = -p.y;
aux.y = p.x;
}
else{
if(k == 2){
aux.x = -p.x;
aux.y = -p.y;
}
else{
if(k == 3){
aux.x = p.y;
aux.y = -p.x;
}
else{
aux = p;
}
}
}
return aux;
}
int cautbin(pair<int, int> p){
int st, dr, mid;
st = 1;
dr = n;
while(st <= dr){
mid = (st + dr) / 2;
if(v[mid].x == p.x && v[mid].y == p.y){
break;
}
else{
if(v[mid].x < p.x || (v[mid].x == p.x && v[mid].y < p.y)){
st = mid + 1;
}
else{
dr = mid - 1;
}
}
}
if(st <= dr){
return mid;
}
return 0;
}
int main(){
fin>> n;
for(i = 1; i <= n; i++){
fin>> v[i].x >> v[i].y;
vv[i] = v[i];
}
sort(v + 1, v + n + 1);
for(k = 0; k < 4; k++){
for(j = 2; j <= n; j++){
p = rotate(v[1], k);
sx = v[j].x - p.x;
sy = v[j].y - p.y;
memset(f, 0, sizeof(f));
memset(w, 0, sizeof(w));
memset(viz, 0, sizeof(viz));
w[1] = j;
f[j] = 1;
for(i = 2; i <= n; i++){
p = rotate(v[i], k);
p.x += sx;
p.y += sy;
mid = cautbin(p);
w[i] = mid;
f[mid] = 1;
}
ok = 1;
for(i = 1; i <= n; i++){
if(f[i] == 0 && viz[i] == 0){
if(lg(i) % 2 == 1){
ok = 0;
break;
}
}
}
if(ok == 0){
continue;
}
for(i = 1; i <= n; i++){
if(viz[i] == 0){
if(lg(i) % 2 == 1){
ok = 0;
break;
}
}
}
if(ok == 1){
for(i = 1; i <= n; i++){
mid = cautbin(vv[i]);
sol[i] = sol1[mid];
}
for(i = 1; i <= n; i++){
fout<< sol[i] <<"\n";
}
return 0;
}
}
}
return 0;
}