Cod sursa(job #3306899)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 15 august 2025 00:48:57
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <iomanip>
// #include <bits/stdc++.h>
#define in  fin
#define out fout

// cowboy in the continental suit - marty robbins e foarte peak

using namespace std;
using db = double;
using ll = long long;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

pair<ll, ll> v[100001];

bool cmpx(pair<ll, ll> &a, pair<ll, ll> &b){
    if(a.first != b.first) return a.first < b.first;
    else return a.second < b.second;
}

bool cmpy(pair<ll, ll> &a, pair<ll, ll> &b){
    return a.second < b.second;
}

db dist(pair<ll, ll> a, pair<ll, ll> b){
    return sqrt( db( (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second) ) );
}

db solve(ll l, ll r){
    if(l == r) return 1e18;
    if(l == r + 1) return dist(v[l], v[r]);

    ll m = (l + r) / 2;
    db dmin = min( solve(l, m), solve(m + 1, r) );

    vector< pair<ll, ll> > cand; // candidati care pot fi la merge
    for(ll i = l; i <= r; i++){
        if( abs(v[i].first - v[m].first) <= dmin ) cand.push_back(v[i]);
    }

    sort(cand.begin(), cand.end(), cmpy);

    for(ll i = 0; i < cand.size(); i++){
        for(ll j = 1; j <= i && dist(cand[i], cand[j]) <= dmin; j++){ // merge si asa daca uit constanta
            dmin = min(dmin, dist(cand[i], cand[i - j]));
        }
    }

    return dmin;
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    ll n; in >> n;
    for(ll i = 0; i < n; i++) in >> v[i].first >> v[i].second;
    sort(v + 0, v + n, cmpx);
    out << fixed << setprecision(6) << solve(0, n - 1) << '\n';


    return 0;
}