Cod sursa(job #1025881)

Utilizator freak93Adrian Budau freak93 Data 10 noiembrie 2013 18:30:11
Problema Overlap Scor 76
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

struct Point {
    int x, y;

    Point rotate90(int many) const {
        Point answer{x, y};
        for (int i = 0; i < many; ++i)
            answer = {-answer.y, answer.x};
        return answer;
    }

    Point operator+(const Point& that) const {
        return {x + that.x, y + that.y};
    }

    Point operator-(const Point& that) const {
        return {x - that.x, y - that.y};
    }

    bool operator<(const Point& that) const {
        if (x != that.x)
            return x < that.x;
        return y < that.y;
    }
};

istream& operator>>(istream& input, Point& object) {
    input >> object.x >> object.y;
    return input;
}

vector<int> check(const vector<Point>& points, int rotate, const Point& shift) {
    map<Point, int> index;
    for (int i = 0; i < int(points.size()); ++i)
        index[points[i]] = i;

    vector<int> next(points.size(), -1), prev(points.size(), -1);
    for (int i = 0; i < int(points.size()); ++i) {
        auto newpoint = points[i].rotate90(rotate) + shift;
        if (index.find(newpoint) == index.end())
            continue;
        next[i] = index[newpoint];
        prev[index[newpoint]] = i;
    }

    // now every chain or path has to be even

    // paths first
    vector<int> answer(points.size(), 0);
    for (int i = 0; i < int(points.size()); ++i)
        if (prev[i] == -1) { // beginning
            int j, type;
            for (j = i, type = 1; j != -1; j = next[j], type = 3 - type)
                answer[j] = type;
            if (type == 2) // odd length path
                return vector<int>();
        }

    // chains now
    for (int i = 0; i < int(points.size()); ++i)
        if (answer[i] == 0) {
            int j, type;
            for (j = i, type = 1; answer[j] == 0; j = next[j], type = 3 - type)
                answer[j] = type;
            if (type == 2) // odd length
                return vector<int>();
        }

    return answer;
}

int main() {
    ifstream cin("overlap.in");
    ofstream cout("overlap.out");

    int N; cin >> N;
    vector<Point> P(N);
    for (int i = 0; i < N; ++i)
        cin >> P[i];

    for (int i = 0; i < 4; ++i) // choose how many times we rotate
        for (int j = 1; j < N; ++j) { // choose the symmetric 
            auto rotate = P.front().rotate90(i);
            auto shift = P[j] - rotate;

            auto answer = check(P, i, shift);
            if (not answer.empty()) {
                for (auto &value : answer)
                    cout << value << "\n";
                return 0;
            }
        }
}