Pagini recente » Cod sursa (job #2866132) | Cod sursa (job #1103332) | Cod sursa (job #1635335) | Cod sursa (job #2511615) | Cod sursa (job #2763838)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
const int NMAX = 1e5;
int N;
pair <int, int> v[NMAX + 2], aux[NMAX + 2];
double ABS(double d) {
return max(d, -d);
}
double dist(pair<int, int> a, pair<int, int> b) {
return sqrtl(1LL * (a.first - b.first) * (a.first - b.first) + 1LL * (a.second - b.second) * (a.second - b.second));
}
double Solve(int st, int dr) {
if(st >= dr) {
return 1e15;
}
int mid = (st + dr) >> 1;
double d1 = Solve(st, mid);
double d2 = Solve(mid + 1, dr);
double d = min(d1, d2);
int k = st, p1 = st, p2 = mid + 1;
while(p1 <= mid || p2 <= dr) {
if(p1 > mid) {
aux[k++] = v[p2++];
} else if(p2 > dr) {
aux[k++] = v[p1++];
} else if(v[p1].second < v[p2].second) {
aux[k++] = v[p1++];
} else {
aux[k++] = v[p2++];
}
}
for(int i = st; i <= dr; i++) {
v[i] = aux[i];
}
k = st - 1;
for(int i = st; i <= dr; i++) {
if(ABS(v[mid].first - v[i].first) <= d) {
aux[++k]= v[i];
}
}
for(int i = st; i <= k; i++) {
for(int j = max(st, i - 7); j < i; j++) {
d = min(d, dist(aux[i], aux[j]));
}
}
return d;
}
int main() {
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> v[i].first >> v[i].second;
}
sort(v + 1, v + N + 1);
cout << fixed << setprecision(6) << Solve(1, N) << '\n';
return 0;
}