Cod sursa(job #2019392)

Utilizator cristina_borzaCristina Borza cristina_borza Data 7 septembrie 2017 17:25:42
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <fstream>
#include <cstring>

using namespace std;

ofstream g ("overlap.out");

const int Nmax = 11800005;
const int Dim = 805;

struct Point {
    int x, y;
} v[ Dim ], aux[ Dim ];

int mp[ Nmax ];

int sin[] = {0, 1, 0, -1};
int cos[] = {1, 0, -1, 0};

int from[ Dim ], to[ Dim ], vis[ Dim ];
int nr, n;

void afis () {
    for (int i = 1; i <= n; ++i) {
        g << vis[i] << '\n';
    }
}

void dfs (int node) {
    int val = 1;
    vis[node] = -1;

    while (from[node] != 0 && vis[from[node]] == 0) {
        node = from[node];
        vis[node] = -1;
    }

    while (node != 0 && vis[node] <= 0) {
        vis[node] = val;
        ++nr;

        if (val == 1)
            val = 2;
        else
            val = 1;

        node = to[node];
    }
}

bool verif (int dx, int dy) {
    memset (from, 0, sizeof (from));
    memset (vis, 0, sizeof (vis));
    memset (to, 0, sizeof (to));

    for (int i = 1; i <= n; ++i) {
        Point paux = aux[i];

        paux.x += dx;
        paux.y += dy;

        if (paux.x * 117 + paux.y >= 0 && paux.x * 117 + paux.y < Nmax) {
            int qw = mp[paux.x * 117 + paux.y];
            if (qw != 0) {
                to[i] = qw;
                from[qw] = i;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (vis[i] == 0) {
            nr = 0;
            dfs (i);

            if (nr % 2 == 1) {
                return false;
            }
        }
    }

    return true;
}

Point rotate (Point p, int k) {
    Point ans;

    int s = sin[k];
    int c = cos[k];

    ans.x = c * p.x - s * p.y;
    ans.y = s * p.x + c * p.y;

    return ans;
}

void read (int &x) {
    char ch;
    int sgn = 1;

    x = 0;

    while (!isdigit(ch = getchar())) {
        if (ch == '-')
            sgn = -1;
        else
            sgn = 1;
    }

    do {
        x = x * 10 + ch - '0';
    }while (isdigit(ch = getchar()));
    x *= sgn;
}

int main() {
    freopen ("overlap.in", "r", stdin);
    read (n);

    for (int i = 1; i <= n; ++i) {
        read (v[i].x), read (v[i].y);
        aux[i] = v[i];
    }

    for (int i = 1; i <= n; ++i) {
        mp[v[i].x * 117 + v[i].y] = i;
    }

    for (int rot = 0; rot < 4; ++rot) {
        for (int i = 1; i <= n; ++i) {
            aux[i] = rotate (v[i], rot);
        }

        for (int i = 2; i <= n; ++i) {
            int dx = v[1].x - aux[i].x;
            int dy = v[1].y - aux[i].y;

            if (verif (dx, dy)) {
                afis ();
                return 0;
            }
        }
    }

    return 0;
}