Cod sursa(job #1134547)

Utilizator dariusdariusMarian Darius dariusdarius Data 6 martie 2014 18:48:35
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
using namespace std;
const int MAX_N = 805;

struct PointXY {
    int x, y;
    PointXY() {}
    PointXY(int xx, int yy): x(xx), y(yy) {}
    inline bool operator < (const PointXY &other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
} points[MAX_N];
int n, group[MAX_N];
int where_to[MAX_N];
int where_from[MAX_N];
bool vis[MAX_N];

inline PointXY rotated(const PointXY &p, int k) {
    if(k == 0) {
        return p;
    } else if(k == 1) {
        return PointXY(-p.y, p.x);
    } else if(k == 2) {
        return PointXY(-p.x, -p.y);
    }
    return PointXY(p.y, -p.x);
}

map<PointXY, int> position;
int dfs_chain(int node) {
    if(where_from[node] == -1 || group[where_from[node]] == 2) {
        group[node] = 1;
    } else {
        group[node] = 2;
    }
    vis[node] = true;
    if(where_to[node] == -1) {
        return 1;
    }
    return 1 + dfs_chain(where_to[node]);
}
int dfs_cycle(int node) {
    if(group[where_from[node]] == 1) {
        group[node] = 2;
    } else {
        group[node] = 1;
    }
    vis[node] = true;
    if(!vis[where_to[node]]) {
        return 1 + dfs_cycle(where_to[node]);
    }
    return 1;
}
bool overlap(int k, int shift_x, int shift_y, int ind) {
    bool debug = (k == 1 && ind == 5);
    debug && cout << "Overlapping with rotation " << k * 90 << " and (" << shift_x << ", " << shift_y << ")\n";
    for(int i = 1; i <= n; ++ i) {
        where_to[i] = where_from[i] = -1;
        vis[i] = false;
    }
    for(int i = 1; i <= n; ++ i) {
        PointXY pair = rotated(points[i], k);
        pair.x += shift_x;
        pair.y += shift_y;
        if(!position.count(pair)) {
        } else {
            where_to[i] = position[pair];
            where_from[position[pair]] = i;
        }
    }
    for(int i = 1; i <= n; ++ i) {
        debug && cout << where_from[i] << " " << where_to[i] << "\n";
    }
    bool condition = true;
    for(int i = 1; i <= n; ++ i) {
        if(where_from[i] == -1) {
            condition &= (dfs_chain(i) % 2 == 0);
        }
    }
    for(int i = 1; i <= n; ++ i) {
        if(!vis[i]) {
            condition &= (dfs_cycle(i) % 2 == 0);
        }
    }
    return condition;
}

int main() {
    ifstream fin("overlap.in");
    ofstream fout("overlap.out");
    fin >> n;
    for(int i = 1; i <= n; ++ i) {
        fin >> points[i].x >> points[i].y;
        position[points[i]] = i;
    }
    for(int k = 0; k < 4; ++ k) {
        for(int i = 2; i <= n; ++ i) {
            if(overlap(k, points[i].x - rotated(points[1], k).x, points[i].y - rotated(points[1], k).y, i)) {
                for(int i = 1; i <= n; ++ i) {
                    fout << group[i] << "\n";
                }
                return 0;
            }
        }
    }
    return 0;
}