Pagini recente » Cod sursa (job #161097) | Istoria paginii blog/doi-la-suta-2008-raport | Cod sursa (job #848635) | Cod sursa (job #596953) | Cod sursa (job #2006327)
#include <bits/stdc++.h>
using namespace std;
const int N = 802;
int n;
struct Point
{
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {};
Point rotated(int degrees)
{
long double dg = (long double)degrees * acos(-1) / 180.0;
int Cos = cos(dg), Sin = sin(dg);
return Point(x * Cos - y * Sin, x * Sin + y * Cos);
}
bool operator < (const Point&that)const
{
return make_pair(x, y) < make_pair(that.x, that.y);
}
bool operator == (const Point &that ) const
{
return x == that.x && y == that.y;
}
};
Point init[N], curr_point[N];
int link[N], multime[N];
bool vis[N];
map < Point, int > pos;
void Solve(int match_1, bool ok)
{
int difx,dify;
if(!ok)
difx = (init[match_1].x - curr_point[1].x), dify = (init[match_1].y - curr_point[1].y);
else
{
difx=(curr_point[match_1].x-init[1].x),dify=curr_point[match_1].y-init[1].y;
}
for(int i = 1; i <= n; ++i)
{
link[i] = 0;
vis[i] = false;
multime[i] = 0;
}
for(int i = 1; i <= n; ++i)
{
Point need = Point(curr_point[i].x + difx, curr_point[i].y + dify);
auto itr = pos.find(need);
if(itr != end(pos))
link[i] = itr->second;
}
int cnt = 0;
for(int i = 1; i <= n; ++i)
{
if(!vis[i] && link[i] )
{
int j = i;
vector < int > reach;
while(j > 0 && !vis[j])
{
++cnt;
reach.push_back(j);
vis[j] = 1;
j = link[j];
}
if(reach.size() % 2)return;
for(int i = 0; i + 1 < reach.size(); i += 2)
{
multime[reach[i]] = 1;
multime[reach[i + 1]] = 2;
}
}
}
if(cnt != n) return;
for(int i = 1; i <= n; ++i)printf("%d\n", multime[i]);
exit(0);
}
int main()
{
freopen("overlap.in", "r", stdin);
freopen("overlap.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
scanf("%d %d", &init[i].x, &init[i].y);
pos[init[i]] = i;
}
for(int rotation = 0; rotation <= 3; ++rotation)
{
for(int i = 1; i <= n; ++i)
{
curr_point[i] = init[i].rotated(rotation * 90);
}
for(int match_1 = 2; match_1 <= n; ++match_1)
{
Solve(match_1,0);Solve(match_1,1);
}
}
return 0;
}