Cod sursa(job #3223826)

Utilizator ReBeGhElRebegea Stefan ReBeGhEl Data 13 aprilie 2024 19:15:35
Problema Overlap Scor 24
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 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[i]=j;
            }
        }
    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;
    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}]++;
            }
        }
        bool ok=0;
        for(auto ax : fr)
        {
            if(ax.second>=n/2)
            {
                if(solve(ax.first))
                    return 0;
            }
        }

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