Cod sursa(job #3277622)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 16 februarie 2025 22:25:07
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.26 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

const int NMAX = 1e5;

int n;
pair<int, int> puncte[1 + NMAX];

vector<int> listaPuncteApropiate;

int calculareIndexSt(int st, int mij, double distMinStDr)
{
    int stCautBin = st;
    int drCautBin = mij;
    int sol = -1;

    while (stCautBin <= drCautBin)
    {
        int mijCautBin = (stCautBin + drCautBin) / 2;

        if (puncte[mij].first - puncte[mijCautBin].first <= distMinStDr)
        {
            sol = mijCautBin;
            drCautBin = mijCautBin - 1;
        }
        else
        {
            stCautBin = mijCautBin + 1;
        }
    }

    if (sol == -1)
        sol = mij + 1;

    return sol;
}

int calculareIndexDr(int mij, int dr, double distMinStDr)
{
    int stCautBin = mij + 1;
    int drCautBin = dr;
    int sol = -1;

    while (stCautBin <= drCautBin)
    {
        int mijCautBin = (stCautBin + drCautBin) / 2;

        if (puncte[mijCautBin].first - puncte[mij].first <= distMinStDr + 1)
        {
            sol = mijCautBin;
            stCautBin = mijCautBin + 1;
        }
        else
        {
            drCautBin = mijCautBin - 1;
        }
    }

    if (sol == -1)
        sol = mij;

    return sol;
}

void generareListaPuncteApropiate(int st, int dr, double distMinStDr)
{
    listaPuncteApropiate.clear();

    int mij = (st + dr) / 2;

    int indexSt = calculareIndexSt(st, mij, distMinStDr);
    int indexDr = calculareIndexDr(mij, dr, distMinStDr);

    int indexCrtSt = indexSt;
    int indexCrtDr = mij + 1;

    while (indexCrtSt <= mij && indexCrtDr <= indexDr)
    {
        if (puncte[indexCrtSt].first == puncte[indexCrtDr].first)
        {
            if (puncte[indexCrtSt].second < puncte[indexCrtDr].second)
            {
                listaPuncteApropiate.push_back(indexCrtSt);
                ++indexCrtSt;
            }
            else
            {
                listaPuncteApropiate.push_back(indexCrtDr);
                ++indexCrtDr;
            }
        }
        else if (puncte[indexCrtSt].first < puncte[indexCrtDr].first)
        {
            listaPuncteApropiate.push_back(indexCrtSt);
            ++indexCrtSt;
        }
        else
        {
            listaPuncteApropiate.push_back(indexCrtDr);
            ++indexCrtDr;
        }
    }
    while (indexCrtSt <= mij)
    {
        listaPuncteApropiate.push_back(indexCrtSt);
        ++indexCrtSt;
    }
    while (indexCrtDr <= indexDr)
    {
        listaPuncteApropiate.push_back(indexCrtDr);
        ++indexCrtDr;
    }
}

double distEuclid(int index0, int index1)
{
    long long distOX = (long long)puncte[index0].first - puncte[index1].first;
    long long distOY = (long long)puncte[index0].second - puncte[index1].second;

    return sqrt(distOX * distOX + distOY * distOY);
}

double distMinRec(int st, int dr)
{
    if (dr - st + 1 <= 3)
    {
        double sol = distEuclid(st, st + 1); /// Ca sa nu folosim o constanta INF.

        for (int i = st; i <= dr; ++i)
        {
            for (int j = i + 1; j <= dr; ++j)
            {
                sol = min(sol, distEuclid(i, j));
            }
        }

        return sol;
    }

    int mij = (st + dr) / 2;

    double distMinSt = distMinRec(st, mij);
    double distMinDr = distMinRec(mij + 1, dr);

    double distMinStDr = min(distMinSt, distMinDr);

    /// Etapa de Combinare

    generareListaPuncteApropiate(st, dr, distMinStDr);

    double sol = distMinStDr;

    for (int i = 0; i < listaPuncteApropiate.size(); ++i)
        for (int j = i + 1; j <= min(i + 7, (int)listaPuncteApropiate.size() - 1); ++j)
            sol = min(sol, distEuclid(listaPuncteApropiate[i], listaPuncteApropiate[j]));

    return sol;
}

int main()
{
    ios_base::sync_with_stdio(false);

    ifstream in("cmap.in");
    ofstream out("cmap.out");
    in.tie(nullptr);
    out.tie(nullptr);

    in >> n;

    for (int i = 1; i <= n; ++i)
    {
        in >> puncte[i].first >> puncte[i].second;
    }

    sort(puncte + 1, puncte + 1 + n);

    out << setprecision(8) << distMinRec(1, n) << '\n';

    in.close();
    out.close();

    return 0;
}