Cod sursa(job #1012719)

Utilizator misinozzz zzz misino Data 19 octombrie 2013 16:00:52
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<fstream>
#include<map>
#include<cstring>
#define N 805
#define x first
#define y second
using namespace std;
ifstream f("overlap.in");
ofstream g("overlap.out");
int nr[N],ok,nx,ny,i,n,k,j,viz[N],gr[N],sol[N];
pair<int,int>p[N],p1,p2;
map<pair<int,int>,int>m;
inline void roteste(pair<int,int> &p,int k)
{
    if(!k)
    return ;
    swap(p.x,p.y);
    p.x=-p.x;
    roteste(p,k-1);
}
inline void punct_nou(pair<int,int> &p,int x,int y)
{
    p.x+=x;
    p.y+=y;
}
inline int nrc(int x,int s)
{
    if(!x||viz[x])
    return 0;
    viz[x]=1;
    sol[x]=s;
    return 1+nrc(gr[x],1^s);
}
inline void afis()
{
    for(i=1;i<=n;++i)
    g<<sol[i]+1<<'\n';
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>p[i].x>>p[i].y;
        m[p[i]]=i;
    }
    for(k=0;k<=3;++k)
    {
        for(i=2;i<=n;++i)
        if(p[i]!=p[1])
        {
            p1=p[i];
            roteste(p1,k);
            nx=p[1].x-p1.x;
            ny=p[1].y-p1.y;
            memset(gr,0,sizeof(gr));
            memset(viz,0,sizeof(viz));
            memset(nr,0,sizeof(nr));
            for(j=1;j<=n;++j)
            {
                p2=p[j];
                roteste(p2,k);
                punct_nou(p2,nx,ny);
                if(m.find(p2)!=m.end())
                gr[j]=m[p2],++nr[gr[j]];
            }
            ok=1;
            for(j=1;j<=n;++j)
            if(!nr[j])
            if(nrc(j,1)%2)
            ok=0;
            for(j=1;j<=n;++j)
            if(!viz[j]&&nr[j]&&nrc(j,1)%2)
            ok=0;
            if(ok)
            {
                afis();
                return 0;
            }
        }
    }
}