Cod sursa(job #1516201)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 2 noiembrie 2015 20:44:40
Problema Overlap Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
  
struct punct{
    int x, y;
    punct(): x(0), y(0){}
    punct(const int X, const int Y): x(X), y(Y){}
    bool operator==(const punct& rhs)const{
        return x == rhs.x && y == rhs.y; } };
  
namespace std{
    template<>
    struct hash<punct>{
        size_t operator()(const punct& p)const{
            return hash<int>()(p.x) ^ (hash<int>()(p.y)<<1); } }; }
  
punct move_point(punct p, int unghi, const punct& dist){
    for( ; unghi > 0; --unghi){
        p = {100000-p.y, p.x}; }
    p.x += dist.x;
    p.y += dist.y;
    return p; }
  
void find_dist(const int cur, vector<int>& next, vector<int>& len_starting, const int first){
    if(next[cur] == -1 || next[cur] == first){
        len_starting[cur] = 1; }
    else{
		if(len_starting[next[cur]] == -1){
			find_dist(next[cur], next, len_starting, first); }
		len_starting[cur] = len_starting[next[cur]]+1; } }
  
int main(){
    ifstream f("overlap.in");
    ofstream g("overlap.out");
    int n;
    f >> n;
    punct base;
    f >> base.x >> base.y;
    unordered_map<punct, int> puncte;
    puncte[punct(0, 0)] = 0;
    for(int i = 1, a, b; i < n; ++i){
        f >> a >> b;
        a -= base.x;
        b -= base.y;
        puncte[punct(a, b)] = i; }
    vector<int> next(n, -1), len_starting(n, -1);
  
    bool is_good = false;
    for(const auto delta : puncte){
        if(!(delta.first == punct(0, 0))){
            for(int unghi = 0; unghi < 4 && !is_good; ++unghi){
                fill(begin(next), end(next), -1);
                fill(begin(len_starting), end(len_starting), -1);
                for(const auto other : puncte){
                    auto it = puncte.find(move_point(other.first, unghi, delta.first));
                    if(it != end(puncte)){
                        next[other.second] = it->second; } }

                is_good = true;
                for(int i = 0; i < n && is_good; ++i){
					if(len_starting[i] == -1){
						find_dist(i, next, len_starting, i);
						if(len_starting[i]%2 == 1){
							is_good = false; } } } }
            if(is_good){
                break; } } }
    for(const auto x : len_starting){
        g << (x%2 + 1) << '\n'; }
    return 0; }