Cod sursa(job #1385099)

Utilizator andreiiiiPopa Andrei andreiiii Data 11 martie 2015 18:09:19
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <bits/stdc++.h>
using namespace std;

const int Nmax = 805;

pair<int, int> A[Nmax];
multimap<pair<int, int>, int> positions;

int G[Nmax], degIn[Nmax];
bool used[Nmax];

vector<int> solve(int N, pair<int, int> angle, int transx, int transy) {
    int cosa = angle.first, sina = angle.second;
    for (int i = 1; i <= N; ++i) {
        degIn[i] = 0;
        used[i] = false;
    }
    for (int i = 1; i <= N; ++i) {
        G[i] = 0;
        
        int nx = round(A[i].first * cosa - A[i].second * sina + transx);
        int ny = round(A[i].first * sina + A[i].second * cosa + transy);

        auto it = positions.find(make_pair(nx, ny));
        if (it != positions.end()) {
            G[i] = it->second;
            degIn[it->second] = 1;
        }
    }

    /*if (transx == 4 && transy == 11 && angle.first == 0 && angle.second == -1) {
        for (int i = 1; i <= N; ++i)
            cerr << G[i] << ' ';
        cerr << '\n';
    }*/

    vector<int> ret;
    for (int i = 1; i <= N; ++i) {
        if (!used[i] && degIn[i] == 0) {
            int size = 0;
            for (int j = i; j != 0 && !used[j]; j = G[j]) {
                if ((size & 1) == 0) ret.push_back(j);
                used[j] = true;
                size++;
            }
            if ((size & 1) != 0) return vector<int>(1, -1);
        }
    }
    for (int i = 1; i <= N; ++i) {
        if (!used[i]) {
            int size = 0;
            for (int j = i; j != 0 && !used[j]; j = G[j]) {
                if ((size & 1) == 0) ret.push_back(j);
                used[j] = true;
                size++;
            }
            if ((size & 1) != 0) return vector<int>(1, -1);
        }
    }
    return ret;
}

vector<int> solveAll(int N, pair<int, int> angle) {
    int cosa = angle.first, sina = angle.second;
    vector<int> ret;
    for (int i = 2; i <= N; ++i) {
        int nx = round(A[i].first * cosa - A[i].second * sina);
        int ny = round(A[i].first * sina + A[i].second * cosa);        
        
        int transx = A[1].first - nx;
        int transy = A[1].second - ny;

        /*if (angle.first == 0 && angle.second == -1 && i == 5) {
            //cerr << transx << ' ' << transy << '\n';
            cerr << cosa << ' ' << sina << '\n';
            cerr << A[i].first << ' ' << A[i].second << '\n';
            cerr << nx << ' ' << ny << '\n';
        }*/

        ret = solve(N, angle, transx, transy);
        if (!(int(ret.size()) == 1 && ret[0] == -1)) break;
    }
    return ret;
}

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

    int N;
    fin >> N;    
    for (int i = 1; i <= N; ++i) {
        fin >> A[i].first >> A[i].second;
        positions.insert(make_pair(A[i], i));
    }

    vector<pair<int, int>> angles = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    vector<int> set1;
    for (auto angle: angles) {
        //cerr << "here\n";
        set1 = solveAll(N, angle);
        if (!(int(set1.size()) == 1 && set1[0] == -1))
            break;
    }
    assert(!(int(set1.size()) == 1 && set1[0] == -1));

    vector<int> ans(N, 1);
    for (int p: set1) ans[p - 1] = 2;

    for (int p: ans) fout << p << '\n';

    fin.close();
    fout.close();
}