Pagini recente » Cod sursa (job #2941921) | Cod sursa (job #1755664) | Cod sursa (job #2300046) | Cod sursa (job #254471) | Cod sursa (job #2061131)
#include <bits/stdc++.h>
#define x first
#define y second
#define Point pair<int,int>
using namespace std;
ifstream fin ("overlap.in");
ofstream fout ("overlap.out");
const int Nmax = 808;
int i, n;
map< Point, int > points;
map< Point, int > :: iterator it;
deque<int> q;
Point a[Nmax], b[Nmax];
bool used[Nmax];
int w[Nmax], go[Nmax];
Point add(Point a, Point b)
{
return {a.x + b.x, a.y + b.y};
}
bool check(int id)
{
int i, j, nr; bool ok;
for(i=1; i<=n; ++i) b[i] = a[i];
for(j=0; j<4; ++j)
{
memset(w, 0, sizeof(w));
memset(used, 0, sizeof(used));
w[1] = 1; w[id] = 2;
for(i=2; i<=n; ++i)
if(i != id)
{
b[i] = {-b[i].y, b[i].x};
it = points.find(add(b[i], a[id]));
if(it == points.end()) go[i] = 0;
else go[i] = it->second, used[it->second] = 1;
}
ok = 1;
for(i=2; ok && i<=n; ++i)
if(i != id && !used[i])
{
nr = i;
while(nr && !w[nr])
{
if(!go[nr] || w[go[nr]])
{
ok = 0;
break;
}
w[nr] = 1;
w[go[nr]] = 2;
nr = go[go[nr]];
}
}
for(i=2; ok && i<=n; ++i)
if(i != id && !w[i])
{
nr = i;
while(nr && !w[nr])
{
if(!go[nr] || w[go[nr]])
{
ok = 0;
break;
}
w[nr] = 1;
w[go[nr]] = 2;
nr = go[go[nr]];
}
}
if(ok) return 1;
}
return 0;
}
int main()
{
fin >> n;
for(i=1; i<=n; ++i)
fin >> a[i].x >> a[i].y;
for(i=n; i; --i)
{
a[i].x -= a[1].x; a[i].y -= a[1].y;
points[a[i]] = i;
}
for(i=2; i<=n; ++i) /// duc a[1] in a[i]
if(check(i))
{
for(i=1; i<=n; ++i) fout << w[i] << '\n';
return 0;
}
return 0;
}