Cod sursa(job #2771524)

Utilizator MarcGrecMarc Grec MarcGrec Data 27 august 2021 20:16:16
Problema Overlap Scor 44
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.57 kb
#define MAX_N 800

#include <iostream>
#include <fstream>
#include <unordered_map>

using namespace std;

ifstream fin("overlap.in");
ofstream fout("overlap.out");

struct point
{
    int x, y;
    
    bool operator== (const point& other) const
    {
        return x == other.x && y == other.y;
    }
    
    size_t operator()(point const& p) const noexcept
    {
        const int64_t x = p.x;
        const int64_t y = p.y;
        return (x | y << 32) % 15485863;
    }

} A[MAX_N + 1], B[MAX_N + 1], C[MAX_N + 1];

struct coord_data
{
    int posib_nerot, posib_rot, sigur_nerot, sigur_rot;
    point nerot_to_rot, rot_to_nerot;
};

int n;

bool Check();
bool SolveCoord(coord_data&, unordered_map<point, coord_data, point>&);
bool Enpair(coord_data&, int, unordered_map<point, coord_data, point>&);

int main()
{
    fin >> n;

    for (int i = 1; i <= n; ++i)
    {
        fin >> A[i].x >> A[i].y;
        B[i] = A[i];
    }

    for (int i = 1; i <= 4; ++i)
    {
        for (int j = 2; j <= n; ++j)
        {
            // A[1] - corespondend cu B[j].

            int dx = B[j].x - A[1].x, dy = B[j].y - A[1].y;

            for (int k = 1; k <= n; ++k)
            {
                C[k].x = B[k].x - dx;
                C[k].y = B[k].y - dy;
            }

            if (Check())
                return 0;
        }

        // Rotatie.
        for (int j = 1; j <= n; ++j)
        {
            swap(B[j].x, B[j].y);
            B[j].x = -B[j].x;
        }
    }

    return 0;
}

bool Check()
{
    // Pentru fiecare coordonate (x, y) tin minte cate puncte am acolo nerotite si rotite.
    unordered_map<point, coord_data, point> M;

    for (int i = 1; i <= n; ++i)
    {
        ++M[A[i]].posib_nerot;
        M[A[i]].nerot_to_rot = C[i];
        ++M[C[i]].posib_rot;
        M[C[i]].rot_to_nerot = A[i];
    }

    for (auto& el : M)
    {
        coord_data& data = el.second;

        if (!SolveCoord(data, M))
            return false;
    }

    // Daca am ajuns aici mai am doar ciclurile de rezolvat.

    for (auto& el : M)
    {
        coord_data& data = el.second;

        if (data.posib_nerot > 0) // Ar trebui ca data.posib_nerot == data.posib_rot
        {
            Enpair(data, data.posib_nerot, M);
        }
    }

    // Daca am ajuns aici am gasit o solutie si o afisez.

    for (int i = 1; i <= n; ++i)
    {
        if (M[A[i]].sigur_nerot > 0)
        {
            fout << 1 << '\n';
            --M[A[i]].sigur_nerot;
        }
        else if (M[C[i]].sigur_rot > 0)
        {
            fout << 2 << '\n';
            --M[C[i]].sigur_rot;
        }
    }

    return true;
}

bool SolveCoord(coord_data& data, unordered_map<point, coord_data, point>& M)
{
    if (data.posib_nerot > data.posib_rot) // Daca am mai multe puncte nerotite inseamna ca sigur nu au pereche toate punctele nerotite, deci o parte sunt 100% rotite.
    {
        int delta = data.posib_nerot - data.posib_rot;

        if (!Enpair(M[data.nerot_to_rot], delta, M)) // Imperechez cele 'delta' puncte rotite, corespondentele celor 'delta' nerotite care stiu ca nu si-ar fi gasit pereche.
            return false;
    }

    else if (data.posib_rot > data.posib_nerot) // Daca am mai multe puncte rotite inseamna ca sigur nu au pereche toate punctele rotite, deci o parte sunt 100% nerotite.
    {
        int delta = data.posib_rot - data.posib_nerot;

        if (!Enpair(M[data.rot_to_nerot], delta, M)) // Imperechez cele 'delta' puncte nerotite, corespondentele celor 'delta' rotite care stiu ca nu si-ar fi gasit pereche.
            return false;
    }

    return true;
}

bool Enpair(coord_data& data, int count, unordered_map<point, coord_data, point>& M)
{
    // La coordonatele descrise de 'data' vreau sa imperechez 'count' puncte.
    data.sigur_nerot += count;
    data.sigur_rot += count;
    data.posib_nerot -= count;
    data.posib_rot -= count;

    coord_data& cor_nerot = M[data.nerot_to_rot]; // Corespondentul rotit al punctului nerotit.
    cor_nerot.posib_rot -= count;

    coord_data& cor_rot = M[data.rot_to_nerot]; // Corespondentul nerotit al punctului rotit.
    cor_rot.posib_nerot -= count;

    if (data.posib_nerot < 0 || data.posib_rot < 0 || cor_nerot.posib_rot < 0 || cor_rot.posib_nerot < 0)
        return false;

    // Continui sa fac verificari pe coordonatele schimbate.
    if (!SolveCoord(data, M)) return false;
    if (!SolveCoord(cor_nerot, M)) return false;
    if (!SolveCoord(cor_rot, M)) return false;

    return true;
}