Pagini recente » Cod sursa (job #134602) | Cod sursa (job #3270145) | Cod sursa (job #6324) | Cod sursa (job #711487) | Cod sursa (job #1385099)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 805;
pair<int, int> A[Nmax];
multimap<pair<int, int>, int> positions;
int G[Nmax], degIn[Nmax];
bool used[Nmax];
vector<int> solve(int N, pair<int, int> angle, int transx, int transy) {
int cosa = angle.first, sina = angle.second;
for (int i = 1; i <= N; ++i) {
degIn[i] = 0;
used[i] = false;
}
for (int i = 1; i <= N; ++i) {
G[i] = 0;
int nx = round(A[i].first * cosa - A[i].second * sina + transx);
int ny = round(A[i].first * sina + A[i].second * cosa + transy);
auto it = positions.find(make_pair(nx, ny));
if (it != positions.end()) {
G[i] = it->second;
degIn[it->second] = 1;
}
}
/*if (transx == 4 && transy == 11 && angle.first == 0 && angle.second == -1) {
for (int i = 1; i <= N; ++i)
cerr << G[i] << ' ';
cerr << '\n';
}*/
vector<int> ret;
for (int i = 1; i <= N; ++i) {
if (!used[i] && degIn[i] == 0) {
int size = 0;
for (int j = i; j != 0 && !used[j]; j = G[j]) {
if ((size & 1) == 0) ret.push_back(j);
used[j] = true;
size++;
}
if ((size & 1) != 0) return vector<int>(1, -1);
}
}
for (int i = 1; i <= N; ++i) {
if (!used[i]) {
int size = 0;
for (int j = i; j != 0 && !used[j]; j = G[j]) {
if ((size & 1) == 0) ret.push_back(j);
used[j] = true;
size++;
}
if ((size & 1) != 0) return vector<int>(1, -1);
}
}
return ret;
}
vector<int> solveAll(int N, pair<int, int> angle) {
int cosa = angle.first, sina = angle.second;
vector<int> ret;
for (int i = 2; i <= N; ++i) {
int nx = round(A[i].first * cosa - A[i].second * sina);
int ny = round(A[i].first * sina + A[i].second * cosa);
int transx = A[1].first - nx;
int transy = A[1].second - ny;
/*if (angle.first == 0 && angle.second == -1 && i == 5) {
//cerr << transx << ' ' << transy << '\n';
cerr << cosa << ' ' << sina << '\n';
cerr << A[i].first << ' ' << A[i].second << '\n';
cerr << nx << ' ' << ny << '\n';
}*/
ret = solve(N, angle, transx, transy);
if (!(int(ret.size()) == 1 && ret[0] == -1)) break;
}
return ret;
}
int main() {
ifstream fin("overlap.in");
ofstream fout("overlap.out");
int N;
fin >> N;
for (int i = 1; i <= N; ++i) {
fin >> A[i].first >> A[i].second;
positions.insert(make_pair(A[i], i));
}
vector<pair<int, int>> angles = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<int> set1;
for (auto angle: angles) {
//cerr << "here\n";
set1 = solveAll(N, angle);
if (!(int(set1.size()) == 1 && set1[0] == -1))
break;
}
assert(!(int(set1.size()) == 1 && set1[0] == -1));
vector<int> ans(N, 1);
for (int p: set1) ans[p - 1] = 2;
for (int p: ans) fout << p << '\n';
fin.close();
fout.close();
}