Cod sursa(job #1289754)

Utilizator assa98Andrei Stanciu assa98 Data 10 decembrie 2014 11:37:54
Problema Overlap Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <cstring>  

#define pe pair<int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;

ifstream fin("overlap.in");
ofstream fout("overlap.out");

const int MAX_N = 810;
const int MOD = 666013;

vector<pair<pe, int> > H[MOD + 10];
bitset<MAX_N> viz;

pe v[MAX_N];

int hashpe(const pe &p) {
    if(p.fi < 0 || p.se < 0) {
        return MOD;
    }
    return (p.fi * 123 + p.se) % MOD;
}

void insert(const pe &p, const int &poz) {
    H[hashpe(p)].push_back(mp(p, poz));
}

int find(const pe &p) {
    for(auto it : H[hashpe(p)]) {
        if(it.fi == p && !viz[it.se]) {
            return it.se;
        }
    }
    return 0;
}


pe rot(pe p) {
    swap(p.fi, p.se);
    p.fi = -p.fi;
    return p;
}

pe pct(pe p, int k, const pe &s) {
    for(int i = 1; i <= k; i++) {
        p = rot(p);
    }
    return mp(p.fi + s.fi, p.se + s.se);
}

int sol[MAX_N];

bool check(int n, int k, pe s) {
    viz.reset();
    memset(sol, 0, sizeof(sol)); 
    viz[0] = true;
    
    int c = 0;
    for(int i = 1; i <= n; i++) {
        if(!viz[i]) {
            pe p = pct(v[i], k, s);
            int poz = find(p);
            if(poz != 0 && !viz[poz]) {
                sol[i] = 1;
                sol[poz] = 2;
                viz[i] = viz[poz] = true;
                c++;
            }
        }
    }
    if(c == n / 2) {
        for(int i = 1; i <= n; i++) {
            fout << sol[i] << '\n';
        }
        return true;
    }
    return false;
}

int main() {
    int n;
    fin >> n;
    for(int i = 1; i <= n; i++) {
        fin >> v[i].fi >> v[i].se;
        insert(v[i], i);
    }
    
    pe p = v[1];
    for(int k = 0; k < 4; k++) {
        for(int i = 2; i <= n; i++) {
            if(check(n, k, mp(v[i].fi - p.fi, v[i].se - p.se))) {
                return 0;
            }
        }
        p = rot(p);
    }
    return 0;
}