Cod sursa(job #3223827)

Utilizator ReBeGhElRebegea Stefan ReBeGhEl Data 13 aprilie 2024 19:28:01
Problema Overlap Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <vector>
#include <map>

using namespace std;

vector < pair < int , int > > original,points;
vector < int > conectat,tip;
map < pair < int , int > , int > fr;

ifstream cin("overlap.in");
ofstream cout("overlap.out");

int n;
void schimbare90(pair < int , int >& a)
{
    swap(a.first,a.second);
    a.first*=(-1);
}

bool solve(pair < int , int > dif)
{
    for(int i=1;i<=n;i++){
        conectat[i]=-1;
        tip[i]=0;
    }


    for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j)
                    continue;
                if( make_pair(original[j].first-points[i].first,original[j].second-points[i].second) == dif )
                    conectat[j]=i;
            }
        }
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n;i++)
    {
        if(tip[i]==0 && conectat[i]!=-1 && tip[conectat[i]]==0)
        {
            cnt1++;
            cnt2++;
            tip[i]=1;
            tip[conectat[i]]=2;
        }
    }

    if(cnt1==n/2)
    {
        for(int i=1;i<=n;i++)
            cout<<tip[i]<<'\n';
        return true;
    }
    return false;
}

int main()
{
    cin>>n;
    points.resize(n+1);
    conectat.resize(n+1);
    tip.resize(n+1);
    for(int i=1;i<=n;i++)
        cin>>points[i].first>>points[i].second;
    original=points;
    pair < int , int > salvat;
    for(int k=0;k<4;k++)
    {
        fr.clear();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j)
                    continue;
                fr[{original[j].first-points[i].first,original[j].second-points[i].second}]++;
                if(fr[{original[j].first-points[i].first,original[j].second-points[i].second}]==n/2)
                    salvat={original[j].first-points[i].first,original[j].second-points[i].second};
            }
        }
        bool ok=0;
        if(solve(salvat))
            return 0;

        for(int i=1;i<=n;i++)
            schimbare90(points[i]);
    }
    return 0;
}