Cod sursa(job #1755298)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 9 septembrie 2016 19:43:25
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 kb
#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;
}