Pagini recente » Istoria paginii utilizator/negreanuvlad | Cod sursa (job #274648) | Cod sursa (job #1514369) | Cod sursa (job #1180296) | Cod sursa (job #2264039)
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
int n, vf;
pair <ll, ll> a[100100], L, wek[100100];
ll dist(const pair <ll, ll> &a, const pair <ll, ll> &b) {
return (a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se);
}
bool cmp(const pair <ll, ll> &a, const pair <ll, ll> &b) {
return a.se < b.se;
}
ll solve(int st, int dr) {
if (dr - st + 1 <= 3) {
ll bst = LLONG_MAX;
for (int i = st; i < dr; i++)
for (int j = i + 1; j <= dr; j++)
bst = min(bst, dist(a[i], a[j]));
return bst;
}
int mid = st + dr >> 1;
ll bst = min(solve(st, mid), solve(mid + 1, dr));
ll v = (a[mid].fi + a[mid + 1].fi) / 2LL;
vf = 0;
for (int i = st; i <= mid; i++)
if ((a[i].fi - v) * (a[i].fi - v) <= bst + 1)
wek[++vf] = a[i];
sort(wek + 1, wek + vf + 1, cmp);
for (int i = 1; i <= vf; i++)
for (int j = i + 1; j <= vf && j - i <= 7; j++)
bst = min(bst, dist(wek[i], wek[j]));
return bst;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
in >> n;
for (int i = 1; i <= n; i++)
in >> a[i].fi >> a[i].se;
sort(a + 1, a + n + 1);
out << fixed << setprecision(6) << sqrt((ld) solve(1, n));
return 0;
}