Pagini recente » Cod sursa (job #1033069) | Cod sursa (job #761465) | Cod sursa (job #255554) | Cod sursa (job #2742044) | Cod sursa (job #810053)
Cod sursa(job #810053)
#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;
}