Pagini recente » Cod sursa (job #3164504) | Cod sursa (job #1451741) | Cod sursa (job #2882827) | Cod sursa (job #3269825) | Cod sursa (job #1185054)
#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 abs(i64 a) {
return max(-a, a);
}
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);
}
void merge(int left, int right) {
int mid = (left + right) / 2, p1 = left, p2 = mid + 1, len = 0;
while (p1 <= mid || p2 <= right)
if (p1 > mid)
aux[++len] = v[p2++];
else if (p2 > right)
aux[++len] = v[p1++];
else if (v[p1].second < v[p2].second)
aux[++len] = v[p1++];
else
aux[++len] = v[p2++];
for (int i = left, j = 1; i <= right; ++i, ++j)
v[i] = aux[j];
}
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]));
sort(v + left, v + 1 + right,
[&] (const pair<int, int> &a, const pair<int, int> &b) {
return a.second < b.second;
}
);
return res;
}
int mid = (left + right) / 2;
res = min(make(left, mid), make(mid + 1, right));
merge(left, right);
int len = 0;
for (int i = left; i <= right; ++i)
if (abs(v[i].first - v[mid].first) <= res)
aux[++len] = v[i];
for (int i = 1; i < len; ++i)
for (int j = i + 1, cnt = 1; cnt <= 7; ++j, ++cnt)
res = min(res, dist(aux[i], aux[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;
}