Cod sursa(job #3196511)

Utilizator not_anduAndu Scheusan not_andu Data 24 ianuarie 2024 10:18:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("03")

using namespace std;

#define INFILE "cmap.in"
#define OUTFILE "cmap.out"

typedef long long ll;

const ll INF = 1e18;
const int N_MAX = 1e5 + 5;

struct Point {

    ll x, y;

    Point() : x(0LL), y(0LL) {}
    Point(ll _x, ll _y) : x(_x), y(_y) {}

};

int n;
ll ans = INF;
Point v[N_MAX];

bool compareX(Point a, Point b){
    return (a.x < b.x);
}

bool compareY(Point a, Point b){
    return (a.y < b.y);
}

ll getDistance(Point a, Point b){
    ll deltaX = (a.x - b.x);
    ll deltaY = (a.y - b.y);
    return (deltaX * deltaX + deltaY * deltaY);
}

void getMinDistance(int left, int right){

    if(left == right) return;

    ll middle = ((left + right) >> 1);

    ll x = v[middle].x;
    vector<Point> pt;

    getMinDistance(left, middle);
    getMinDistance(middle + 1, right);

    for(int i = left; i <= right; ++i){
        if((v[i].x - x) * (v[i].x - x) <= ans) pt.push_back(v[i]);
    }

    sort(pt.begin(), pt.end(), compareY);

    for(int i = 0; i < pt.size(); ++i){
        for(int j = i + 1; j < pt.size(); ++j){
            if((pt[j].y - pt[i].y) * (pt[j].y - pt[i].y) > ans) break;
            ans = min(ans, getDistance(pt[i], pt[j]));
        }
    }

}

void solve(){

    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> v[i].x >> v[i].y;
    }

    sort(v + 1, v + n + 1, compareX);

    getMinDistance(1, n);

    long double result = sqrt((long double)ans);
    cout << fixed << setprecision(6) << result << '\n';

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}