Cod sursa(job #3273334)

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

#pragma GCC optimize("Ofast,unroll-loops")

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

long long dist2(Pont p1, Pont p2)
{
    long long dx = p1.first - p2.first;
    long long 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];
}

inline void rendezy(vector<Pont> &t, int bal, int jobb)
{
    for (int i = bal+1; i <= jobb; i++) {
        Pont temp = t[i];
        int j = i;
        while (j > bal && ycomp(temp, t[j-1])) {
            t[j] = t[j-1];
            j--;
        }
        t[j] = temp;
    }
}


long long 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];
        rendezy(ty, bal, jobb);

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

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

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

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

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

        Pont buf[7];
        int nbuf = min(7, jobb-bal+1);
        int ibuf = 0;

        for (int i = bal; i <= jobb; i++)
            if (abs(t[i].first - xkozep) <= dmin) {
                for (int j = 0; j < ibuf; j++) {
                    long long d = dist2(ty[i], buf[j]);
                    if (d < dmin)
                        dmin = d;

                    if (ibuf == nbuf && j > 0)
                        buf[j-1] = buf[j];
                }

                if (ibuf < nbuf) {
                    buf[ibuf] = ty[i];
                    ibuf++;
                }
                else {
                    buf[nbuf-1] = ty[i];
                }
            }

        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;
}