Cod sursa(job #810053)

Utilizator ChallengeMurtaza Alexandru Challenge Data 9 noiembrie 2012 15:28:14
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>
#include <map>
#include <cstring>

using namespace std;

const char InFile[]="overlap.in";
const char OutFile[]="overlap.out";
const int MaxN=805;

ifstream fin(InFile);
ofstream fout(OutFile);

struct Point
{
	int x,y;

	bool operator< (const Point &a) const
	{
		if(x==a.x)
		{
			return y<a.y;
		}
		return x<a.x;
	}
};

int N,Next[MaxN],Deg[MaxN],SOL[MaxN];
char viz[MaxN];
bool good;
Point P[MaxN];
map<Point,int> H;

inline Point Rotate(Point p, int rot)
{
	int px,py;
	for(register int steps=0;steps<rot;++steps)
	{
		px=p.x;
		py=p.y;
		p.x=-py;
		p.y=px;
	}
	return p;
}

inline void Mark(int x)
{
	int cnt=0;
	while(!viz[x])
	{
		viz[x]=1;
		++cnt;
		SOL[x]=1+(cnt&1);
		x=Next[x];
	}
	if(cnt&1)
	{
		good=false;
	}
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>P[i].x>>P[i].y;
		H[P[i]]=i;
	}
	fin.close();

	for(register int rot=0;rot<4;++rot)
	{
		for(register int i=2;i<=N;++i)
		{
			Point p=Rotate(P[i],rot);
			int dispX=P[1].x-p.x;
			int dispY=P[1].y-p.y;

			memset(Next,0,sizeof(Next));
			memset(Deg,0,sizeof(Deg));
			memset(viz,0,sizeof(viz));
			viz[0]=1;

			for(register int j=1;j<=N;++j)
			{
				Point p=Rotate(P[j],rot);
				p.x+=dispX;
				p.y+=dispY;
				if(H.find(p)!=H.end())
				{
					Next[j]=H[p];
					++Deg[Next[j]];
				}
			}

			good=true;
			for(register int i=1;i<=N;++i)
			{
				if(Deg[i]==0)
				{
					Mark(i);
				}
			}

			for(register int i=1;i<=N;++i)
			{
				if(!viz[i])
				{
					Mark(i);
				}
			}

			if(good)
			{
				goto afis;
			}
		}
	}

afis:
	for(register int i=1;i<=N;++i)
	{
		fout<<SOL[i]<<"\n";
	}
	fout.close();
	return 0;
}