Cod sursa(job #918162)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 17:52:36
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 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;
}