#include <fstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>
#include <tuple>
struct point
{
int x;
int y;
point(int _x, int _y)
: x(_x)
, y(_y)
{}
};
struct x_pred
{
bool operator()(const point& lhs, const point& rhs)
{
return lhs.x < rhs.x;
}
};
struct y_pred
{
bool operator()(const point& lhs, const point& rhs)
{
return lhs.y < rhs.y;
}
};
double euclid_dist(const point& lhs, const point& rhs)
{
return std::sqrt(1LL*(lhs.x - rhs.x)*(lhs.x - rhs.x) +
1LL*(lhs.y - rhs.y)*(lhs.y - rhs.y));
}
double brute_force_impl(const std::vector<point>& x_points,
std::vector<point>& points,
int low,
int high)
{
auto min_dist = std::numeric_limits<double>::max();
for (auto i = low; i < high; ++i)
for (auto j = i + 1; j <= high; ++j)
min_dist = std::min(min_dist, euclid_dist(x_points[i], x_points[j]));
std::sort(points.begin() + low, points.begin() + high, y_pred{});
return min_dist;
}
double smallest_crossing(const std::vector<point>& y_points,
double gamma,
const point& ref,
int low,
int high)
{
std::vector<point> y_prime;
for (auto i = low; i <= high; ++i)
if (std::abs(y_points[i].x - ref.x) <= gamma)
y_prime.push_back(y_points[i]);
auto min_dist = std::numeric_limits<double>::max();
for (auto i = 0; i < static_cast<int>(y_prime.size()) - 1; ++i)
for (auto j = i + 1; j < static_cast<int>(y_prime.size()) &&
j - i < 8; ++j)
min_dist = std::min(min_dist, euclid_dist(y_prime[i], y_prime[j]));
return min_dist;
}
void merge_points(std::vector<point> &points, int low, int mid, int high)
{
std::vector<point> aux_points;
auto i = low, j = mid + 1;
while (i <= mid && j <= high)
aux_points.push_back(
points[i].y < points[j].y ? points[i++] : points[j++]
);
while (i <= mid)
aux_points.push_back(points[i++]);
while (j <= high)
aux_points.push_back(points[j++]);
for (int q = low; q <= high; ++q)
points[q] = aux_points[q - low];
}
double smallest_dist_impl(const std::vector<point>& x_points,
std::vector<point>& y_points,
int low,
int high)
{
if (high - low < 3)
return brute_force_impl(x_points, y_points, low, high);
auto mid = (low + high)/2;
auto gamma = std::min(
smallest_dist_impl(x_points, y_points, low, mid),
smallest_dist_impl(x_points, y_points, mid + 1, high)
);
merge_points(y_points, low, mid, high);
return std::min(
gamma,
smallest_crossing(y_points, gamma, x_points[mid], low, high)
);
}
double smallest_dist(const std::vector<point>& x_points,
std::vector<point>& y_points)
{
return smallest_dist_impl(x_points, y_points, 0, x_points.size() - 1);
}
int main()
{
std::ifstream fin{"cmap.in"};
std::ofstream fout{"cmap.out"};
int N;
fin >> N;
std::vector<point> points_x;
for (auto i = 0; i < N; ++i) {
int x, y;
fin >> x >> y;
points_x.emplace_back(x, y);
}
std::sort(points_x.begin(), points_x.end(), x_pred{});
auto y_points = points_x;
fout << std::setprecision(6) << std::fixed
<< smallest_dist(points_x, y_points);
return 0;
}