Pagini recente » Cod sursa (job #2515852) | Cod sursa (job #2610051) | Cod sursa (job #2579421) | Cod sursa (job #2493997) | Cod sursa (job #2500314)
#include <bits/stdc++.h>
#define x first
#define y second
const int MAX_N = 100005;
const double INF = 1.0 * MAX_N * MAX_N;
int n;
std::pair <double, double> arr[MAX_N];
bool operator < (const std::pair <double, double> &a,
const std::pair <double, double> &b) {
if (a.x == b.x) {
return a.y < b.y;
} else {
return a.x < b.x;
}
}
double distance(std::pair <double, double> a,
std::pair <double, double> b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double dei(int lo, int ri) {
std::vector <std::pair <double, double>> points;
double min = INF, lo_ans, ri_ans;
int len = ri - lo + 1, mid = (lo + ri) >> 1, ri_p, lo_p;
if (len <= 3) {
for (int i = lo; i <= ri; ++i) {
points.push_back(arr[i]);
}
for (int i = 0; i < points.size(); ++i) {
for (int j = i + 1; j < points.size(); ++j) {
min = std::min(min, distance(points[i], points[j]));
}
}
return min;
}
lo_ans = dei(lo, mid);
ri_ans = dei(mid + 1, ri);
min = std::min(lo_ans, ri_ans);
lo_p = ri_p = mid;
while (distance(arr[mid], arr[lo_p]) <= min) {
--lo_p;
}
++lo_p;
while (distance(arr[mid], arr[ri_p]) <= min) {
++ri_p;
}
--ri_p;
for (int i = lo_p; i <= ri_p; ++i) {
points.push_back(arr[i]);
}
for (int i = 0; i < points.size(); ++i) {
for (int j = i + 1; j < points.size(); ++j) {
min = std::min(min, distance(arr[i], arr[j]));
}
}
return min;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::cin >> arr[i].x >> arr[i].y;
}
std::sort(arr + 1, arr + n + 1);
std::cout << std::fixed << std::setprecision(6) << dei(1, n);
return 0;
}