Pagini recente » Cod sursa (job #2298208) | Cod sursa (job #804642) | Cod sursa (job #628) | Cod sursa (job #804641) | Cod sursa (job #1185043)
#include <algorithm>
#include <cmath>
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long long i64;
const i64 inf = 1LL << 61;
const int MaxN = 100005;
int n;
pair<int, int> v[MaxN], aux[MaxN];
inline i64 dist(const pair<int, int> &a, const pair<int, int> &b) {
return 1LL * (a.first - b.first) * (a.first - b.first) + 1LL * (a.second - b.second) * (a.second - b.second);
}
i64 make(int left, int right) {
i64 res = inf;
if (right - left <= 2) {
for (int i = left; i <= right; ++i)
for (int j = i + 1; j <= right; ++j)
res = min(res, dist(v[i], v[j]));
return res;
}
int mid = (left + right) / 2;
res = min(make(left, mid), make(mid + 1, right));
sort(v + left, v + 1 + right,
[&] (const pair<int, int> &a, const pair<int, int> &b) {
return a.second < b.second;
}
);
for (int i = left; i <= right; ++i)
for (int j = i + 1, cnt = 0; cnt <= 7 && j <= right; ++j)
res = min(res, dist(v[i], v[j]));
return res;
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i].first >> v[i].second;
sort(v + 1, v + 1 + n,
[&] (const pair<int, int> &a, const pair<int, int> &b) {
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
);
fout << fixed << setprecision(6) << sqrt(make(1, n)) << '\n';
fin.close(); fout.close(); return 0;
}