Cod sursa(job #2236776)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 30 august 2018 15:39:17
Problema Overlap Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<fstream>
#include<map>
#define x first
#define y second
using namespace std;
ifstream fi("overlap.in");
ofstream fo("overlap.out");
int n,i,k,j,tx,ty,St[805],Dr[805],Rez[805],ind,b,nr;
map<pair<int,int>,int> M;
pair<int,int> A[805],B[805];
int main()
{
    fi>>n;
    for(i=1; i<=n; i++)
    {
        fi>>A[i].x>>A[i].y;
        B[i]=A[i];
        M[A[i]]=i;
    }
    for(k=1; k<=4; k++)
    {
        for(i=1; i<=n; i++)
        {
            swap(B[i].x,B[i].y);
            B[i].x=-B[i].x;
        }
        for(i=2; i<=n; i++)
        {
            for(j=1; j<=n; j++)
                St[j]=Dr[j]=Rez[j]=0;
            tx=B[1].x-A[i].x;
            ty=B[1].y-A[i].y;
            Dr[1]=i;
            St[i]=1;
            for(j=2; j<=n; j++)
                if(j!=i && M[{B[j].x-tx,B[j].y-ty}]!=0)
                {
                    ind=M[{B[j].x-tx,B[j].y-ty}];
                    Dr[j]=ind;
                    St[ind]=j;
                }
            b=0;
            for(j=1; j<=n; j++)
            {
                if(!Rez[j])
                {
                    ind=j;
                    while(St[ind] && St[ind]!=j)
                        ind=St[ind];
                    nr=0;
                    while(ind && !Rez[ind])
                    {
                        Rez[ind]=nr%2+1;
                        ind=Dr[ind];
                        nr++;
                    }
                    if(nr%2)
                    {
                        b=1;
                        break;
                    }
                }
            }
            if(b==0)
            {
                for(j=1; j<=n; j++)
                    fo<<Rez[j]<<"\n";
                fi.close();
                fo.close();
                return 0;
            }
        }
    }
    fi.close();
    fo.close();
    return 0;
}