Pagini recente » Cod sursa (job #2041239) | Cod sursa (job #897752) | Cod sursa (job #1475084) | Cod sursa (job #448995) | Cod sursa (job #2266083)
#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;
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));
vector < pair < ld, ld > > strip;
for(int i = s; i < e; ++i) {
if(abs(points[mid].first - points[i].first) < dist) {
strip.emplace_back(points[i]);
}
}
sort(strip.begin(), strip.end(), [&](const pair < ld, ld > &a, const pair < ld, ld > &b) {
return a.second < b.second;
});
for(int i = 0; i < (int)strip.size(); ++i) {
for(int j = i + 1; j < min(i + 10, (int)strip.size()); ++j) {
dist = min(dist, getDistance(strip[i], strip[j]));
}
}
return dist;
}
int main() {
int n; fin >> n;
points.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;
}