Cod sursa(job #2019431)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 7 septembrie 2017 19:04:33
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <fstream>
#include <unordered_map>
#include <cstring>

using namespace std;

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

const int nmax = 800;
const int mod = 666013;

struct pct {
    int x, y;

    pct() {}
    pct (int _x, int _y) {
        x = _x, y = _y;
    }

    inline bool operator == (const pct &k) const {
        return x == k.x && y == k.y;
    }
} v[nmax + 1];

struct Hash {
    size_t operator () (const pct &a) const {
        return 1LL * a.x * mod + a.y;
    }
};

int nxt[nmax + 1], cul[nmax + 1];
bool viz[nmax + 1], intra[nmax + 1];
unordered_map<pct, int, Hash> h;

inline pct rot (pct a, int b) {
    for (int i = 1; i <= b; ++ i) {
        swap(a.x, a.y);
        a.x *= -1;
    }
    return a;
}

int main() {
    int n;
    fin >> n;

    for (int i = 1; i <= n; ++ i) {
        fin >> v[ i ].x >> v[ i ].y;
        h[ v[ i ] ] = i;
    }

    for (int k = 0; k < 4; ++ k) {
        pct cpy = rot(v[ 1 ], k);
        for (int j = 2; j <= n; ++ j) {
            int dx, dy;
            dx = v[ j ].x - cpy.x;
            dy = v[ j ].y - cpy.y;

            memset(nxt, 0, sizeof(nxt));
            memset(intra, 0, sizeof(intra));

            for (int i = 1; i <= n; ++ i) {
                pct aux = rot(v[ i ], k);
                aux.x += dx, aux.y += dy;

                if (h.find(aux) != h.end()) {
                    nxt[ i ] = h[ aux ];
                    intra[ nxt[ i ] ] = 1;
                }
            }

            memset(viz, 0, sizeof(viz));

            bool ok = 1;
            for (int i = 1; i <= n; ++ i) {
                if (intra[ i ] == 0) {
                    int lg = 0, x = i;

                    while (x != 0) {
                        ++ lg;
                        viz[ x ] = 1;
                        cul[ x ] = 2 - lg % 2;
                        x = nxt[ x ];
                    }

                    if (lg % 2 == 1) ok = 0;
                }
            }

            for (int i = 1; i <= n; ++ i) {
                if (viz[ i ] == 0) {
                    int lg = 0, x = i;

                    do {
                        ++ lg;
                        viz[ x ] = 1;
                        cul[ x ] = 2 - lg % 2;
                        x = nxt[ x ];
                    } while (x != i);

                    if (lg % 2 == 1) ok = 0;
                }
            }

            if (ok == 1) {
                for (int i = 1; i <= n; ++ i) {
                    fout << cul[ i ] << "\n";
                }
                return 0;
            }
        }
    }

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