Pagini recente » Cod sursa (job #2012615) | Cod sursa (job #3033414) | Cod sursa (job #53417) | Cod sursa (job #2982783) | Cod sursa (job #1134547)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
using namespace std;
const int MAX_N = 805;
struct PointXY {
int x, y;
PointXY() {}
PointXY(int xx, int yy): x(xx), y(yy) {}
inline bool operator < (const PointXY &other) const {
return x < other.x || (x == other.x && y < other.y);
}
} points[MAX_N];
int n, group[MAX_N];
int where_to[MAX_N];
int where_from[MAX_N];
bool vis[MAX_N];
inline PointXY rotated(const PointXY &p, int k) {
if(k == 0) {
return p;
} else if(k == 1) {
return PointXY(-p.y, p.x);
} else if(k == 2) {
return PointXY(-p.x, -p.y);
}
return PointXY(p.y, -p.x);
}
map<PointXY, int> position;
int dfs_chain(int node) {
if(where_from[node] == -1 || group[where_from[node]] == 2) {
group[node] = 1;
} else {
group[node] = 2;
}
vis[node] = true;
if(where_to[node] == -1) {
return 1;
}
return 1 + dfs_chain(where_to[node]);
}
int dfs_cycle(int node) {
if(group[where_from[node]] == 1) {
group[node] = 2;
} else {
group[node] = 1;
}
vis[node] = true;
if(!vis[where_to[node]]) {
return 1 + dfs_cycle(where_to[node]);
}
return 1;
}
bool overlap(int k, int shift_x, int shift_y, int ind) {
bool debug = (k == 1 && ind == 5);
debug && cout << "Overlapping with rotation " << k * 90 << " and (" << shift_x << ", " << shift_y << ")\n";
for(int i = 1; i <= n; ++ i) {
where_to[i] = where_from[i] = -1;
vis[i] = false;
}
for(int i = 1; i <= n; ++ i) {
PointXY pair = rotated(points[i], k);
pair.x += shift_x;
pair.y += shift_y;
if(!position.count(pair)) {
} else {
where_to[i] = position[pair];
where_from[position[pair]] = i;
}
}
for(int i = 1; i <= n; ++ i) {
debug && cout << where_from[i] << " " << where_to[i] << "\n";
}
bool condition = true;
for(int i = 1; i <= n; ++ i) {
if(where_from[i] == -1) {
condition &= (dfs_chain(i) % 2 == 0);
}
}
for(int i = 1; i <= n; ++ i) {
if(!vis[i]) {
condition &= (dfs_cycle(i) % 2 == 0);
}
}
return condition;
}
int main() {
ifstream fin("overlap.in");
ofstream fout("overlap.out");
fin >> n;
for(int i = 1; i <= n; ++ i) {
fin >> points[i].x >> points[i].y;
position[points[i]] = i;
}
for(int k = 0; k < 4; ++ k) {
for(int i = 2; i <= n; ++ i) {
if(overlap(k, points[i].x - rotated(points[1], k).x, points[i].y - rotated(points[1], k).y, i)) {
for(int i = 1; i <= n; ++ i) {
fout << group[i] << "\n";
}
return 0;
}
}
}
return 0;
}