Pagini recente » Profil poky | Cod sursa (job #205648) | Cod sursa (job #1440524) | Cod sursa (job #1186870) | Cod sursa (job #2074230)
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const int nmax=1004;
struct point
{
int x;
int y;
bool operator <(const point &aux) const
{
if(x!=aux.x) return (x<aux.x);
return y<aux.y;
}
}v[nmax],v2[nmax];
map<point,int>ap;
int n;
int p[nmax],p2[nmax],val[nmax],vis[nmax];
inline void citeste()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i].x,&v[i].y);
ap[v[i]]=i;
}
}
point rotate_90(point a)
{
point b;
b.x=-a.y;
b.y=a.x;
return b;
}
int dfs(int nod,int vlt)
{
vis[nod]=1;
if(val[nod]==0)
{
val[nod]=vlt;
if(p[nod]!=-1) return dfs(p[nod],3-vlt);
else
{
if(vlt==1) return 0;
return 1;
}
}
else
{
if(val[nod]!=vlt) return 0;
return 1;
}
}
int try_for(int rot,int transx,int transy)
{
for(int i=1;i<=n;i++)
{
val[i]=0;
vis[i]=0;
v2[i]=v[i];
for(int j=1;j<=rot;j++) v2[i]=rotate_90(v2[i]);
v2[i].x+=transx;
v2[i].y+=transy;
if(ap[v2[i]]==0) p[i]=-1;
else p[i]=ap[v2[i]];
}
int as=0;
for(int i=1;i<=n;i++)
{
if(p[i]==-1) continue;
if(!vis[i])
{
if(dfs(i,1)==0)
{
// if(transx==11&&transy==-2) printf("!%d!",i);
as=1;
break;
}
}
}
for(int i=1;i<=n;i++) if(!vis[i]) return 0;
as=1-as;
return as;
}
void print_solution()
{
for(int i=1;i<=n;i++) printf("%d\n",val[i]);
}
inline void do_for_rotation_and_translation()
{
point temp=v[1];
for(int j=1;j<=3;j++)
{
temp=rotate_90(temp);
for(int i=1;i<=n;i++)
{
if(try_for(j,v[i].x-temp.x,v[i].y-temp.y))
{
print_solution();
return;
}
}
}
}
int main()
{
freopen ("overlap.in","r",stdin);
freopen ("overlap.out","w",stdout);
citeste();
do_for_rotation_and_translation();
}