Cod sursa(job #2019347)

Utilizator cristina_borzaCristina Borza cristina_borza Data 7 septembrie 2017 16:18:30
Problema Overlap Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <map>

using namespace std;

ifstream f ("overlap.in");
ofstream g ("overlap.out");

const double Pi = 3.1415926535897932;
const double Eps = 0.000001;

const int Dim = 805;

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

map <pair <int, int>, int> mp;

double sin[] = {0, 1, 0, -1};
double 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;

        int qw = mp[{paux.x , 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;

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


    double px = c * (double)p.x - s * (double)p.y;
    double py = s * (double)p.x + c * (double)p.y;

    ans.x = (int) px;
    ans.y = (int) py;

    return ans;
}

int main() {
    f >> n;

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

    for (int i = 1; i <= n; ++i) {
        mp[{v[i].x, 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;
}