Pagini recente » Cod sursa (job #579175) | Cod sursa (job #2308858) | Cod sursa (job #2293771) | Cod sursa (job #3293096) | Cod sursa (job #2712598)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("overlap.in");
ofstream fout("overlap.out");
struct pair_hash {
template<class T1, class T2>
size_t operator() (const pair<T1, T2> &p) const {
return hash<T1>()(p.first)^hash<T2>()(p.second);
}
};
const int NMAX = 808;
int N, x, y, prv[NMAX], nxt[NMAX], sol[NMAX];
pair<int,int> p[NMAX], init[NMAX];
unordered_map<pair<int,int>,int,pair_hash> match;
int main() {
fin >> N;
for(int i = 1; i <= N; ++i) {
fin >> x >> y;
init[i] = p[i] = make_pair(x, y);
match[init[i]] = i;
}
// rotatie trigonometrica la 90 de grade: (-y, x)
// rotatie in sensul acelor de ceasornic la 90 de grade: (y, -x)
for(int rep = 0; rep < 4; ++rep) {
for(int i = 1; i <= N; ++i) {
swap(p[i].first, p[i].second);
p[i].second *= -1;
}
for(int i = 2; i <= N; ++i) {
int diffx = init[i].first - p[1].first,
diffy = init[i].second - p[1].second;
memset(prv, 0, sizeof(prv));
memset(nxt, 0, sizeof(nxt));
memset(sol, 0, sizeof(sol));
for(int j = 1; j <= N; ++j)
if(i != j && match[make_pair(p[j].first + diffx, p[j].second + diffy)]) {
int index = match[make_pair(p[j].first + diffx, p[j].second + diffy)];
nxt[j] = index;
prv[index] = j;
}
bool ok = true;
for(int j = 1; j <= N && ok; ++j) {
int curr = j;
while(prv[curr] && prv[curr] != j)
curr = prv[curr];
bool colour = false;
while(!sol[curr] && curr) {
sol[curr] = colour + 1;
colour ^= 1;
curr = nxt[curr];
}
if(colour)
ok = false;
}
if(ok) {
for(int j = 1; j <= N; ++j)
fout << sol[j] << '\n';
return 0;
}
}
}
}