Cod sursa(job #562706)

Utilizator DraStiKDragos Oprica DraStiK Data 23 martie 2011 18:42:58
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <algorithm>
using namespace std;

#define mp make_pair
#define sc second
#define fs first

#define DIM 805
#define LIM 4

int viz[DIM],f[DIM],ind[DIM],sol[DIM];
pair <int,int> v[DIM];
int N;

void read ()
{
    int i;

    scanf ("%d",&N);
    for (i=1; i<=N; ++i)
    {
        scanf ("%d%d",&v[i].fs,&v[i].sc);
        ind[i]=i;
    }
}

struct cmp
{
    bool operator () (const int &a,const int &b) const
    {
        return v[a]<v[b];
    }
};

inline pair <int,int> rotatie (pair <int,int> p,int k)
{
    pair <int,int> newp;


    if (!k)
        newp=p;
    else if (k==1)
        newp=mp (p.sc,-p.fs);
    else if (k==2)
        newp=mp (-p.fs,-p.sc);
    else
        newp=mp (-p.sc,p.fs);

    return newp;
}

inline int c_bin (pair <int,int> val)
{
    int st,dr,mij;

    for (st=1, dr=N; st<=dr; )
    {
        mij=(st+dr)>>1;

        if (v[mij]==val)
        {
            if (!viz[mij])
                return mij;

            return 0;
        }
        else if (v[mij]<val)
            st=mij+1;
        else
            dr=mij-1;
    }

    return 0;
}

inline int got_sol ()
{
    int i,j,nrp;

    for (i=1; i<=N; ++i)
        if (!viz[i])
            return 0;

    memset (viz,0,sizeof (viz));

    for (i=1; i<=N; ++i)
        if (!viz[i] && f[i])
        {
            nrp=0;
            for (j=i; j && !viz[j]; j=f[j])
                viz[j]=1, sol[ind[j]]=nrp+1, nrp^=1;

            if (nrp)
                return 0;
        }

    return 1;
}

void solve ()
{
    pair <int,int > pct,dir;
    int i,j,k,poz;

    sort (ind+1,ind+N+1,cmp ());
    sort (v+1,v+N+1);

    for (k=0; k<LIM; ++k)
        for (i=2; i<=N; ++i)
        {
            memset (viz,0,sizeof (viz));
            memset (f,0,sizeof (f));

            pct=rotatie (v[1],k);
            dir.fs=v[i].fs-pct.fs;
            dir.sc=v[i].sc-pct.sc;
            viz[1]=viz[i]=1;
            f[1]=i;

            for (j=2; j<=N; ++j)
                if (!viz[j])
                {
                    pct=rotatie (v[j],k);
                    pct.fs+=dir.fs;
                    pct.sc+=dir.sc;

                    poz=c_bin (pct);
                    if (poz)
                    {
                        viz[j]=viz[poz]=1;
                        f[j]=poz;
                    }
                }

            if (got_sol ())
                return ;
        }
}

void print ()
{
    int i;

    for (i=1; i<=N; ++i)
        printf ("%d\n",sol[i]);
}

int main ()
{
    freopen ("overlap.in","r",stdin);
    freopen ("overlap.out","w",stdout);

    read ();
    solve ();
    print ();

    return 0;
}