Pagini recente » Cod sursa (job #1035197) | Cod sursa (job #3153989) | Cod sursa (job #347656) | Cod sursa (job #376918) | Cod sursa (job #2019347)
#include <iostream>
#include <fstream>
#include <cstring>
#include <map>
using namespace std;
ifstream f ("overlap.in");
ofstream g ("overlap.out");
const double Pi = 3.1415926535897932;
const double Eps = 0.000001;
const int Dim = 805;
struct Point {
int x, y;
} v[ Dim ], aux[ Dim ];
map <pair <int, int>, int> mp;
double sin[] = {0, 1, 0, -1};
double 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;
int qw = mp[{paux.x , 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;
double s = sin[k];
double c = cos[k];
double px = c * (double)p.x - s * (double)p.y;
double py = s * (double)p.x + c * (double)p.y;
ans.x = (int) px;
ans.y = (int) py;
return ans;
}
int main() {
f >> n;
for (int i = 1; i <= n; ++i) {
f >> v[i].x >> v[i].y;
aux[i] = v[i];
}
for (int i = 1; i <= n; ++i) {
mp[{v[i].x, 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;
}