Cod sursa(job #3277633)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 16 februarie 2025 23:21:39
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.9 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;

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

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

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

        vector<int> sortareY;

        if (dr - st + 1 == 2)
        {
            sol = min(sol, distEuclid(st, st + 1));

            if (puncte[st].second < puncte[st + 1].second)
            {
                sortareY.push_back(st);
                sortareY.push_back(st + 1);
            }
            else
            {
                sortareY.push_back(st + 1);
                sortareY.push_back(st);
            }
        }
        else /// Este sigur 3.
        {
            sol = min(sol,
                      min(distEuclid(st, st + 1),
                            min(distEuclid(st, st + 2),
                                distEuclid(st + 1, st + 2)
                      )));

            sortareY.push_back(st);
            sortareY.push_back(st + 1);
            sortareY.push_back(st + 2);

            if (puncte[st].second > puncte[st + 1].second)
                swap(sortareY[0], sortareY[1]);
            if (puncte[st + 1].second > puncte[st + 2].second)
                swap(sortareY[1], sortareY[2]);
            if (puncte[st].second > puncte[st + 1].second)
                swap(sortareY[0], sortareY[1]);
        }

        return make_pair(sol, sortareY);
    }

    int mij = (st + dr) / 2;

    pair<double, vector<int>> solSt = distMinRec(st, mij);
    pair<double, vector<int>> solDr = distMinRec(mij + 1, dr);

    double distMinStDr = min(solSt.first, solDr.first);

    /// Etapa de Combinare

    vector<int> sortareOY;

    int indexSortSt = 0;
    int indexSortDr = 0;
    while (indexSortSt < solSt.second.size() && indexSortDr < solDr.second.size())
    {
        if (puncte[solSt.second[indexSortSt]].second < puncte[solDr.second[indexSortDr]].second)
        {
            sortareOY.push_back(solSt.second[indexSortSt]);
            ++indexSortSt;
        }
        else
        {
            sortareOY.push_back(solDr.second[indexSortDr]);
            ++indexSortDr;
        }
    }
    while (indexSortSt < solSt.second.size())
    {
        sortareOY.push_back(solSt.second[indexSortSt]);
        ++indexSortSt;
    }
    while (indexSortDr < solDr.second.size())
    {
        sortareOY.push_back(solDr.second[indexSortDr]);
        ++indexSortDr;
    }

    listaPuncteApropiate.clear();
    for (int i = 0; i < (int)sortareOY.size(); ++i)
        if (abs(puncte[sortareOY[i]].first - puncte[mij].first) < distMinStDr)
            listaPuncteApropiate.push_back(sortareOY[i]);

    /// Final

    double sol = distMinStDr;

    for (int i = 0; i < (int)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 make_pair(sol, sortareOY);
}

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(6) << fixed << distMinRec(1, n).first << '\n';

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

    return 0;
}