Pagini recente » Cod sursa (job #177415) | Cod sursa (job #1730921) | Cod sursa (job #1214366) | Cod sursa (job #2028748) | Cod sursa (job #2266089)
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const ld INF = 1e13;
vector < pair < ld, ld > > points;
vector < pair < ld, ld > > strip;
ld getDistance(const pair < ld, ld > &a, const pair < ld, ld > &b) {
return sqrtl((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
ld Solve(int s, int e) {
if(s + 1 >= e) return INF;
int mid = (s + e) / 2;
ld dist = min(Solve(s, mid), Solve(mid, e));
int idx = 0;
for(int i = s; i < e; ++i) {
if(abs(points[mid].first - points[i].first) < dist) {
strip[idx++] = points[i];
}
}
sort(strip.begin(), strip.begin() + idx, [&](const pair < ld, ld > &a, const pair < ld, ld > &b) {
return a.second < b.second;
});
for(int i = 0; i < idx; ++i) {
for(int j = i + 1; j < min(i + 8, idx); ++j) {
dist = min(dist, getDistance(strip[i], strip[j]));
}
}
return dist;
}
int main() {
ios::sync_with_stdio(false);
fin.tie(0); fout.tie(0);
int n; fin >> n;
points.resize(n); strip.resize(n);
for(int i = 0; i < n; ++i) {
fin >> points[i].first >> points[i].second;
}
sort(points.begin(), points.end());
fout << fixed << setprecision(10) << Solve(0, n);
return 0;
}