Cod sursa(job #1803940)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 12 noiembrie 2016 00:49:04
Problema Overlap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <cstdio>
#include <map>

using namespace std;


struct punct
{
    int x,y;
};

punct v[810],v1[810];
int v2[810],rez[810];
char vaz1[810],vaz2[810];
map<pair<int,int>,int> vaz;

void rotire(int i,int type)
{
    if(type==1) v1[i]={v[i].x,v[i].y};
    else if(type==2) {v1[i].x=-v[i].y;v1[i].y=v[i].x;}
    else if(type==3) {v1[i].x=-v[i].x;v1[i].y=-v[i].y;}
    else if(type==4) {v1[i].x=v[i].y;v1[i].y=-v[i].x;}
}


int main()
{
    freopen("overlap.in","r",stdin);
    freopen("overlap.out","w",stdout);
    int n,a,b,p,c,s;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].x,&v[i].y);
        vaz[{v[i].x,v[i].y}]=i;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=4;j++)
        {
            rotire(1,j);
            a=v[i].x-v1[1].x;
            b=v[i].y-v1[1].y;
            v1[1].x+=a;v1[1].y+=b;
            v2[1]=i;
            vaz2[i]=1;
            p=0;s=0;
            for(int k=2;k<=n;k++)
            {
                rotire(k,j);
                v1[k].x+=a;
                v1[k].y+=b;
                if(vaz.count({v1[k].x,v1[k].y})==0 or (v1[k].x==v[k].x && v1[k].y==v[k].y)) v2[k]=-1;
                else {v2[k]=vaz[{v1[k].x,v1[k].y}];vaz2[v2[k]]=1;}
            }
            for(int k=1;k<=n;k++)
                if(vaz2[k]==0)
                {
                    vaz1[k]=1;c=1;
                    a=v2[k];
                    rez[k]=c;
                    while(a!=-1 && vaz1[a]==0) {c++;rez[a]=c;vaz1[a]=1;a=v2[a];}
                    if(c%2==1) {p=1;break;}
                }
            for(int k=1;k<=n;k++)
                if(vaz1[k]==0)
                {
                    vaz1[k]=1;c=1;
                    a=v2[k];
                    rez[k]=c;
                    while(a!=-1 && vaz1[a]==0) {c++;rez[a]=c;vaz1[a]=1;a=v2[a];}
                    if(c%2==1) {p=1;break;}
                }
            if(p==1)
                for(int k=1;k<=n;k++) {vaz1[k]=0;rez[k]=0;vaz2[k]=0;}
            else
            {
                for(int k=1;k<=n;k++) if(rez[k]%2==1) printf("1\n");
                                        else printf("2\n");
                return 0;
            }
        }
    }
    return 0;
}