Pagini recente » Cod sursa (job #2828835) | Cod sursa (job #2517981) | Cod sursa (job #2755810) | Cod sursa (job #2579392) | Cod sursa (job #2824358)
#include <bits/stdc++.h>
using namespace std;
inline void Open(const string Name) {
#ifndef ONLINE_JUDGE
(void)!freopen((Name + ".in").c_str(), "r", stdin);
(void)!freopen((Name + ".out").c_str(), "w", stdout);
#endif
}
typedef long long i64;
typedef pair <i64, i64> pii;
const i64 INF = 2e18;
vector <pii> V(100001), X, Y;
i64 dist(const pii &a, const pii &b) {
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
i64 go(int st, int dr, vector <pii> &X, vector <pii> Y) {
if(st >= dr - 1)
return INF;
else if(dr - st == 2) {
if(Y[st] > Y[st + 1])
swap(Y[st], Y[st + 1]);
return dist(X[st], X[st + 1]);
}
int mid = (st + dr) / 2;
i64 best = min(go(st, mid, X, Y), go(mid, dr, X, Y));
sort(Y.begin() + st, Y.begin() + dr);
int v_size = 0;
for(int i = st;i < dr;i++)
if(abs(Y[i].second - X[mid].first) <= best)
V[v_size++] = Y[i];
for(int i = 0;i < v_size - 1;i++)
for(int j = i + 1;j < v_size && j - i < 8;j++)
best = min(best, dist(V[i], V[j]));
return best;
}
void solve() {
int N; cin >> N;
X.resize(N), Y.resize(N);
for(int i = 0;i < N;i++)
cin >> X[i].first >> X[i].second;
sort(X.begin(), X.end());
for(int i = 0;i < N;i++)
Y[i] = make_pair(X[i].second, X[i].first);
cout << fixed << setprecision(6) << sqrt(go(0, N, X, Y));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Open("cmap");
int T = 1;
for(;T;T--) {
solve();
}
return 0;
}