Pagini recente » Cod sursa (job #1079867) | Cod sursa (job #2678769) | Cod sursa (job #92343) | Cod sursa (job #2684941) | Cod sursa (job #2837879)
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MAXN = 100000;
lli dist(pair<lli, lli> p1, pair<lli, lli> p2) {
lli x1 = p1.first;
lli y1 = p1.second;
lli x2 = p2.first;
lli y2 = p2.second;
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
int n;
pair<lli, lli> v[MAXN + 2];
lli calcMinDist(pair<lli, lli> v[], int le, int ri) {
int nrEl = ri - le + 1;
int mid = (le + ri) / 2;
if (nrEl <= 3) {
lli minDist = 9e18;
for (int i = le; i <= ri; ++ i)
for (int j = i + 1; j <= ri; ++ j)
minDist = min(minDist, dist(v[i], v[j]));
return minDist;
} else {
lli minDist = min(calcMinDist(v, le, mid), calcMinDist(v, mid + 1, ri));
vector<pair<lli, lli> > m;
lli d = (v[mid].first + v[mid + 1].first) / 2;
for (int i = mid; i >= le && abs(d - v[i].first) <= minDist; -- i)
m.push_back(make_pair(v[i].second, v[i].first));
for (int i = mid + 1; i <= ri && abs(d - v[i].first) <= minDist; ++ i)
m.push_back(make_pair(v[i].second, v[i].first));
sort(m.begin(), m.end());
for (int i = 0; i < m.size(); ++ i)
for (int j = i + 1; j < m.size() && j <= i + 7; ++ j)
minDist = min(minDist, dist(m[i], m[j]));
return minDist;
}
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; ++ i) {
cin >> v[i].first >> v[i].second;
}
sort(v, v + n);
lli distSquared = calcMinDist(v, 0, n - 1);
cout << fixed << setprecision(6) << sqrt(double(distSquared)) << '\n';
return 0;
}