Pagini recente » Istoria paginii utilizator/hardtopronounce | Istoria paginii utilizator/arrowbasse | Cod sursa (job #647029) | Monitorul de evaluare | Cod sursa (job #2019431)
#include <fstream>
#include <unordered_map>
#include <cstring>
using namespace std;
ifstream fin ("overlap.in"); ofstream fout ("overlap.out");
const int nmax = 800;
const int mod = 666013;
struct pct {
int x, y;
pct() {}
pct (int _x, int _y) {
x = _x, y = _y;
}
inline bool operator == (const pct &k) const {
return x == k.x && y == k.y;
}
} v[nmax + 1];
struct Hash {
size_t operator () (const pct &a) const {
return 1LL * a.x * mod + a.y;
}
};
int nxt[nmax + 1], cul[nmax + 1];
bool viz[nmax + 1], intra[nmax + 1];
unordered_map<pct, int, Hash> h;
inline pct rot (pct a, int b) {
for (int i = 1; i <= b; ++ i) {
swap(a.x, a.y);
a.x *= -1;
}
return a;
}
int main() {
int n;
fin >> n;
for (int i = 1; i <= n; ++ i) {
fin >> v[ i ].x >> v[ i ].y;
h[ v[ i ] ] = i;
}
for (int k = 0; k < 4; ++ k) {
pct cpy = rot(v[ 1 ], k);
for (int j = 2; j <= n; ++ j) {
int dx, dy;
dx = v[ j ].x - cpy.x;
dy = v[ j ].y - cpy.y;
memset(nxt, 0, sizeof(nxt));
memset(intra, 0, sizeof(intra));
for (int i = 1; i <= n; ++ i) {
pct aux = rot(v[ i ], k);
aux.x += dx, aux.y += dy;
if (h.find(aux) != h.end()) {
nxt[ i ] = h[ aux ];
intra[ nxt[ i ] ] = 1;
}
}
memset(viz, 0, sizeof(viz));
bool ok = 1;
for (int i = 1; i <= n; ++ i) {
if (intra[ i ] == 0) {
int lg = 0, x = i;
while (x != 0) {
++ lg;
viz[ x ] = 1;
cul[ x ] = 2 - lg % 2;
x = nxt[ x ];
}
if (lg % 2 == 1) ok = 0;
}
}
for (int i = 1; i <= n; ++ i) {
if (viz[ i ] == 0) {
int lg = 0, x = i;
do {
++ lg;
viz[ x ] = 1;
cul[ x ] = 2 - lg % 2;
x = nxt[ x ];
} while (x != i);
if (lg % 2 == 1) ok = 0;
}
}
if (ok == 1) {
for (int i = 1; i <= n; ++ i) {
fout << cul[ i ] << "\n";
}
return 0;
}
}
}
fin.close();
fout.close();
return 0;
}