Cod sursa(job #3350806)

Utilizator Ilinca_Radu_2022Radu Ilinca-Rucsandra Ilinca_Radu_2022 Data 13 aprilie 2026 13:14:25
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define punct pair<int, int>
#define ld long double
#define INF 1e18
#define MAXN 200005
#define epsilon 0.5
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int BULAN=7;
punct v[MAXN];
int n;
vector<punct>x;
int dist(punct a, punct b) {
    return (a.fi-b.fi)*(a.fi-b.fi)+(a.se-b.se)*(a.se-b.se);
}
int solve(int a, int b) {
    int ans=INF;
    if (b-a<3) {
        for (int i=a; i<=b; i++) {
            for (int j=i+1; j<=b; j++) {
                ans=min(ans, dist(v[i], v[j]));
            }
        }
        return ans;
    }
    ans=min(solve(a, (a+b)/2), solve((a+b)/2+1, b));
    ld verticala=(v[(a+b)/2+1].fi+v[(a+b)/2].fi)/2;
    x.clear();
    for (int i=a; i<=b; i++) {
        if ((v[i].fi-verticala)*(v[i].fi-verticala)<=ans+epsilon) x.push_back({v[i].se, v[i].fi});
    }
    sort(x.begin(), x.end());
    int m=x.size();
    for (int i=0; i<m; i++) {
        for (int j=i+1; j<=min(m-1, i+BULAN); j++) {
            ans=min(ans, dist(x[i], x[j]));
        }
    }
    return ans;
}
signed main()
{
    fin>>n;
    for (int i=0; i<n; i++) {
        fin>>v[i].fi>>v[i].se;
    }
    sort(v, v+n);
    fout<<fixed<<setprecision(8)<<sqrt(solve(0, n-1));
    return 0;
}