Cod sursa(job #3223828)

Utilizator ReBeGhElRebegea Stefan ReBeGhEl Data 13 aprilie 2024 19:45:08
Problema Overlap Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <fstream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

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

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;
        }
    }

    queue < int > q;
    for(int i=1;i<=n;i++){
        if(conectat[i]==-1)
            q.push(i);
    }
    while(!q.empty())
    {
        bool ok=0;
        if(tip[q.front()])
        {
            q.pop();
            continue;
        }
        for(int i=1;i<=n;i++)
        {
            if(tip[i]==0 && conectat[i]==q.front())
            {
                tip[q.front()]=1;
                tip[i]=2;
                conectat[i]=-1;
                ok=1;
                break;
            }
        }

        if(ok==0)
            return 0;
        for(int i=1;i<=n;i++)
        {
            if(conectat[i]==-1)
                q.push(i);
        }
        q.pop();
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(tip[i])
            cnt++;
    }
    if(cnt==n)
    {
        for(int i=1;i<=n;i++)
            cout<<tip[i]<<'\n';
        return 1;
    }
    return 0;
}

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++)
    {
        for(int i=1;i<=1;i++)
        {
            for(int j=2;j<=n;j++)
            {
                if(i==j)
                    continue;
                pair < int , int > temp = {original[j].first-points[i].first,original[j].second-points[i].second};
                if(solve(temp))
                    return 0;
            }
        }
        for(int i=1;i<=n;i++)
            schimbare90(points[i]);
    }
    return 0;
}