Pagini recente » Cod sursa (job #3282372) | Cod sursa (job #1865845) | Cod sursa (job #783983) | Cod sursa (job #2901285) | Cod sursa (job #1289754)
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <cstring>
#define pe pair<int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
ifstream fin("overlap.in");
ofstream fout("overlap.out");
const int MAX_N = 810;
const int MOD = 666013;
vector<pair<pe, int> > H[MOD + 10];
bitset<MAX_N> viz;
pe v[MAX_N];
int hashpe(const pe &p) {
if(p.fi < 0 || p.se < 0) {
return MOD;
}
return (p.fi * 123 + p.se) % MOD;
}
void insert(const pe &p, const int &poz) {
H[hashpe(p)].push_back(mp(p, poz));
}
int find(const pe &p) {
for(auto it : H[hashpe(p)]) {
if(it.fi == p && !viz[it.se]) {
return it.se;
}
}
return 0;
}
pe rot(pe p) {
swap(p.fi, p.se);
p.fi = -p.fi;
return p;
}
pe pct(pe p, int k, const pe &s) {
for(int i = 1; i <= k; i++) {
p = rot(p);
}
return mp(p.fi + s.fi, p.se + s.se);
}
int sol[MAX_N];
bool check(int n, int k, pe s) {
viz.reset();
memset(sol, 0, sizeof(sol));
viz[0] = true;
int c = 0;
for(int i = 1; i <= n; i++) {
if(!viz[i]) {
pe p = pct(v[i], k, s);
int poz = find(p);
if(poz != 0 && !viz[poz]) {
sol[i] = 1;
sol[poz] = 2;
viz[i] = viz[poz] = true;
c++;
}
}
}
if(c == n / 2) {
for(int i = 1; i <= n; i++) {
fout << sol[i] << '\n';
}
return true;
}
return false;
}
int main() {
int n;
fin >> n;
for(int i = 1; i <= n; i++) {
fin >> v[i].fi >> v[i].se;
insert(v[i], i);
}
pe p = v[1];
for(int k = 0; k < 4; k++) {
for(int i = 2; i <= n; i++) {
if(check(n, k, mp(v[i].fi - p.fi, v[i].se - p.se))) {
return 0;
}
}
p = rot(p);
}
return 0;
}