Cod sursa(job #1238396)

Utilizator george_stelianChichirim George george_stelian Data 6 octombrie 2014 21:13:02
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

struct punct
{
    int x,y;
    bool operator <(const punct &aux) const
    {
        if(x==aux.x) return y<aux.y;
        else return x<aux.x;
    }
}v[810];
map<punct,int>m;
int obtin[810],n,a;
char vaz[810],sol[810],nr[810];

void roteste(punct &p,int k)
{
    if(!k) return;
    swap(p.x,p.y);
    p.x=-p.x;
    roteste(p,k-1);
}

void buildsol(int x,int s)
{
    if(!x || vaz[x]) return;
    vaz[x]=1;
    sol[x]=s;
    a++;
    buildsol(obtin[x],3-s);
}

int main()
{
    freopen("overlap.in", "r", stdin);
    freopen("overlap.out", "w", stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].x,&v[i].y);
        m[v[i]]=i;
    }
    for(int k=0;k<4;k++)
    {
        for(int i=2;i<=n;i++)
        {
            memset(vaz,0,sizeof(vaz));
            memset(obtin,0,sizeof(obtin));
            memset(nr,0,sizeof(nr));
            punct p=v[i];
            roteste(p,k);
            int difx=v[1].x-p.x,dify=v[1].y-p.y;
            for(int j=1;j<=n;j++)
            {
                punct p1=v[j];
                roteste(p1,k);
                p1.x+=difx;p1.y+=dify;
                if(m.find(p1)!=m.end()) {obtin[j]=m[p1];nr[obtin[j]]=1;}
            }
            int ok=1;
            for(int j=1;j<=n;j++)
                if(!nr[j])
                {
                    a=0;
                    buildsol(j,1);
                    if(a%2) {ok=0;break;}
                }
            for(int j=1;j<=n;j++)
                if(!vaz[j]&&nr[j])
                {
                    a=0;
                    buildsol(j,1);
                    if(a%2) {ok=0;break;}
                }
            if(ok)
            {
                for(int j=1;j<=n;j++) printf("%d\n",sol[j]);
                return 0;
            }
        }
    }
    return 0;
}