Cod sursa(job #3273321)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 1 februarie 2025 17:14:16
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 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;
}

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


double megold(int bal, int jobb, vector<Pont> &t)
{
    if (jobb-bal+1 <= 3) {
        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);
        double dmin_jobb = megold(kozep+1, jobb, t);
        double dmin = min(dmin_bal, dmin_jobb);

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

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

        sort(ty.begin(), ty.end(), ycomp);

        int ns = ty.size();
        for (int i = 0; i < ns; i++) {
            for (int j = 1; j <= 7 && i+j < ns; j++) {
                double d = dist2(ty[i], ty[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;

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

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

    return 0;
}