Cod sursa(job #1238357)

Utilizator george_stelianChichirim George george_stelian Data 6 octombrie 2014 20:04:40
Problema Overlap Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 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 n,ok;
char vaz[810],sol[810];

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

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;
    }
    sol[1]=2;
    for(int k=0;k<4 && !ok;k++)
    {
        for(int i=2;i<=n && !ok;i++)
        {
            memset(vaz,0,sizeof(vaz));
            ok=1;
            vaz[1]=1;
            punct p=v[i];
            roteste(p,k);
            int difx=v[1].x-p.x,dify=v[1].y-p.y;
            sol[i]=1;
            vaz[i]=1;
            for(int j=1;j<=n;j++)
                if(!vaz[j])
                {
                    punct p1=v[j];
                    roteste(p1,k);
                    p1.x+=difx;p1.y+=dify;
                    if(m.find(p1)!=m.end())
                    {
                        int x=m[p1];
                        if(!vaz[x])
                        {
                            sol[j]=1;
                            sol[x]=2;
                            vaz[j]=vaz[x]=1;
                        }
                        else {ok=0;break;}
                    }
                    else {ok=0;break;}
                }
        }
    }
    for(int i=1;i<=n;i++) printf("%d\n",sol[i]);
    return 0;
}