Cod sursa(job #1516229)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 2 noiembrie 2015 21:06:49
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 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 = {-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>& prev, vector<int>& len_starting, const int first){
	if(next[cur] == -1){
        len_starting[cur] = 1; }
	else if(next[cur] == first){
		len_starting[cur] = 1;
		prev[first] = -1;
		next[cur] = -1; }
    else{
		if(len_starting[next[cur]] == -1){
			find_dist(next[cur], next, prev, 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), prev(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(prev), end(prev), -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;
                        prev[it->second] = other.second; } }

                is_good = true;
                for(int i = 0; i < n && is_good; ++i){
					if(len_starting[i] == -1){
						find_dist(i, next, prev, len_starting, i);
						if(prev[i] == -1 && 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; }