Cod sursa(job #3226258)

Utilizator SSKMFSS KMF SSKMF Data 20 aprilie 2024 19:10:50
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.02 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

ifstream cin ("cmap.in");
ofstream cout ("cmap.out");

pair <int , int> coordonate[100001] , temporar[100001];

struct Comparatie {
    bool operator ()(const pair <int , int> optiune_1 , const pair <int , int> optiune_2) const 
    { 
        return optiune_1.second != optiune_2.second ? optiune_1.second < optiune_2.second : optiune_1.first < optiune_2.first;
    }
};

int64_t Distanta (const pair <int , int> punct_1 , const pair <int , int> punct_2)
{
    return (int64_t)(punct_1.first - punct_2.first) * (punct_1.first - punct_2.first) + (int64_t)(punct_1.second - punct_2.second) * (punct_1.second - punct_2.second);
}

int64_t Cauta (const int stanga , const int dreapta)
{
    if (dreapta <= stanga)
        { return INT64_MAX; }

    if (dreapta - stanga == 2)
    {
        if (Comparatie()(coordonate[stanga] , coordonate[dreapta]))
            { swap(coordonate[stanga] , coordonate[dreapta]); }

        return Distanta(coordonate[stanga] , coordonate[dreapta]);
    }
    
    const int mijloc = (stanga + dreapta) >> 1 , pivot = coordonate[mijloc].first;
    int64_t minim = min(Cauta(stanga , mijloc) , Cauta(mijloc + 1 , dreapta));

    int indice_1 = stanga , indice_2 = mijloc + 1 , indice_3 = 0;
    while (indice_1 <= mijloc && indice_2 <= dreapta) {
        if (Comparatie()(coordonate[indice_1] , coordonate[indice_2])) { temporar[++indice_3] = coordonate[indice_1++]; }
        else { temporar[++indice_3] = coordonate[indice_2++]; }
    }
    while (indice_1 <= mijloc) 
        { temporar[++indice_3] = coordonate[indice_1++]; }
    while (indice_2 <= dreapta) 
        { temporar[++indice_3] = coordonate[indice_2++]; }
    
    for (indice_2 = stanga , indice_3 = 1 ; indice_2 <= dreapta ; indice_2++ , indice_3++)
        { coordonate[indice_2] = temporar[indice_3]; }

    int cantitate = 0;
    for (int indice = stanga ; indice <= dreapta ; indice++) {
        if ((int64_t)abs(coordonate[indice].first - pivot) * abs(coordonate[indice].first - pivot) <= minim)
            { temporar[++cantitate] = coordonate[indice]; }
    }

    for (int indice = 1 ; indice < cantitate ; indice++) {
        for (int _indice = indice + 1 ; _indice <= min(cantitate , indice + 7) ; _indice++)
            { minim = min(minim , Distanta(temporar[indice] , temporar[_indice])); }
    }

    return minim;
}

int main ()
{
    int numar_puncte;
    cin >> numar_puncte;

    for (int indice = 1 ; indice <= numar_puncte ; indice++)
        { cin >> coordonate[indice].first >> coordonate[indice].second; }

    sort(coordonate + 1 , coordonate + numar_puncte + 1 , [] (const pair <int , int> optiune_1 , const pair <int , int> optiune_2) -> bool {
        return optiune_1.first != optiune_2.first ? optiune_1.first < optiune_2.first : optiune_1.second < optiune_2.second;
    });

    cout << fixed << setprecision(6) << sqrt(Cauta(1 , numar_puncte));
    cout.close(); cin.close();
    return 0;
}