Cod sursa(job #3273323)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 1 februarie 2025 17:26:38
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.65 kb
//#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");
//ifstream fin("input.txt");
//ofstream fout("output.txt");

typedef pair<int, int> Pont; // .first = x,  .second = y

double dist2(Pont p1, Pont p2)
{
    double dx = p1.first - p2.first;
    double dy = p1.second - p2.second;
    return dx*dx + dy*dy;
}

inline bool ycomp(Pont p1, Pont p2)
{
    return p1.second < p2.second
        || (p1.second == p2.second && p1.first < p2.first);
}

void osszefesul(
    vector<Pont> &ty, int bal, int kozep, int jobb, vector<Pont> &temp)
{
    // temp[bal]...temp[jobb]
    int itemp = bal;

    int ib = bal;
    int ij = kozep+1;

    while (ib <= kozep || ij <= jobb) {
        if (ib <= kozep && (ij > jobb || ycomp(ty[ib], ty[ij]))) {
            temp[itemp] = ty[ib];
            itemp++;
            ib++;
        }
        else {
            temp[itemp] = ty[ij];
            itemp++;
            ij++;
        }
    }

    for (int i = bal; i <= jobb; i++)
        ty[i] = temp[i];
}


double megold(int bal, int jobb, vector<Pont> &t, vector<Pont> &ty)
{
    if (jobb-bal+1 <= 3) {
        for (int i = bal; i <= jobb; i++)
            ty[i] = t[i];
        sort(ty.begin()+bal, ty.begin()+jobb+1, ycomp);

        double dmin = dist2(t[bal], t[bal+1]);

        for (int i = bal; i <= jobb; i++)
            for (int j = i+1; j <= jobb; j++) {
                double d = dist2(t[i], t[j]);
                if (d < dmin)
                    dmin = d;
            }

        return dmin;
    }
    else {
        int kozep = (bal+jobb) / 2;
        int xkozep = t[kozep].first;

        double dmin_bal = megold(bal, kozep, t, ty);
        double dmin_jobb = megold(kozep+1, jobb, t, ty);
        double dmin = min(dmin_bal, dmin_jobb);

        osszefesul(ty, bal, kozep, jobb, t);

        vector<Pont> tyjo;
        tyjo.reserve(jobb-bal+1);

        for (int i = bal; i <= jobb; i++)
            if (abs(t[i].first - xkozep) <= dmin)
                tyjo.push_back(t[i]);

        int ns = tyjo.size();
        for (int i = 0; i < ns; i++) {
            for (int j = 1; j <= 7 && i+j < ns; j++) {
                double d = dist2(tyjo[i], tyjo[i+j]);
                if (d < dmin)
                    dmin = d;
            }
        }

        return dmin;
    }
}


int main()
{
    int n;
    fin >> n;

    vector<Pont> t(n);
    for (int i = 0; i < n; i++)
        fin >> t[i].first >> t[i].second;

    vector<Pont> ty(n);

    sort(t.begin(), t.end());

    fout << fixed << setprecision(7) << sqrt(megold(0, n-1, t, ty)) << endl;

    return 0;
}