Cod sursa(job #1693375)

Utilizator sucureiSucureiRobert sucurei Data 22 aprilie 2016 23:10:03
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 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;
}