Pagini recente » Cod sursa (job #1336992) | Cod sursa (job #1932053) | Cod sursa (job #1649448) | Cod sursa (job #1281185) | Cod sursa (job #2019392)
#include <fstream>
#include <cstring>
using namespace std;
ofstream g ("overlap.out");
const int Nmax = 11800005;
const int Dim = 805;
struct Point {
int x, y;
} v[ Dim ], aux[ Dim ];
int mp[ Nmax ];
int sin[] = {0, 1, 0, -1};
int cos[] = {1, 0, -1, 0};
int from[ Dim ], to[ Dim ], vis[ Dim ];
int nr, n;
void afis () {
for (int i = 1; i <= n; ++i) {
g << vis[i] << '\n';
}
}
void dfs (int node) {
int val = 1;
vis[node] = -1;
while (from[node] != 0 && vis[from[node]] == 0) {
node = from[node];
vis[node] = -1;
}
while (node != 0 && vis[node] <= 0) {
vis[node] = val;
++nr;
if (val == 1)
val = 2;
else
val = 1;
node = to[node];
}
}
bool verif (int dx, int dy) {
memset (from, 0, sizeof (from));
memset (vis, 0, sizeof (vis));
memset (to, 0, sizeof (to));
for (int i = 1; i <= n; ++i) {
Point paux = aux[i];
paux.x += dx;
paux.y += dy;
if (paux.x * 117 + paux.y >= 0 && paux.x * 117 + paux.y < Nmax) {
int qw = mp[paux.x * 117 + paux.y];
if (qw != 0) {
to[i] = qw;
from[qw] = i;
}
}
}
for (int i = 1; i <= n; ++i) {
if (vis[i] == 0) {
nr = 0;
dfs (i);
if (nr % 2 == 1) {
return false;
}
}
}
return true;
}
Point rotate (Point p, int k) {
Point ans;
int s = sin[k];
int c = cos[k];
ans.x = c * p.x - s * p.y;
ans.y = s * p.x + c * p.y;
return ans;
}
void read (int &x) {
char ch;
int sgn = 1;
x = 0;
while (!isdigit(ch = getchar())) {
if (ch == '-')
sgn = -1;
else
sgn = 1;
}
do {
x = x * 10 + ch - '0';
}while (isdigit(ch = getchar()));
x *= sgn;
}
int main() {
freopen ("overlap.in", "r", stdin);
read (n);
for (int i = 1; i <= n; ++i) {
read (v[i].x), read (v[i].y);
aux[i] = v[i];
}
for (int i = 1; i <= n; ++i) {
mp[v[i].x * 117 + v[i].y] = i;
}
for (int rot = 0; rot < 4; ++rot) {
for (int i = 1; i <= n; ++i) {
aux[i] = rotate (v[i], rot);
}
for (int i = 2; i <= n; ++i) {
int dx = v[1].x - aux[i].x;
int dy = v[1].y - aux[i].y;
if (verif (dx, dy)) {
afis ();
return 0;
}
}
}
return 0;
}