Pagini recente » Cod sursa (job #1367071) | Cod sursa (job #2105419) | Cod sursa (job #880984) | Cod sursa (job #1794157) | Cod sursa (job #2058528)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
struct Point{
int x, y;
};
const double inf = 4000000000.0;
double dist(const Point &A, const Point &B) {
return sqrt((1.0 * A.x - B.x) * (A.x - B.x) + (1.0 * A.y - B.y) * (A.y - B.y));
}
double solve_median(int m, double d, int l, int r, vector<Point> &p) {
vector<Point> v;
for (int i = m; i >= l; --i)
if (p[m].x - d >= p[i].x)
v.push_back(p[i]);
for (int i = m; i <= r; ++i)
if (p[m].x + d >= p[i].x)
v.push_back(p[i]);
sort(v.begin(), v.end(), [](const Point &A, const Point &B) -> bool {
return A.y < B.y;
});
for (int i = 0; i < v.size(); ++i)
for (int j = i + 1; j <= v.size() && j <= i + 5; ++j) {
d = min(d, dist(v[i], v[j]));
}
return d;
}
double solve(int l, int r, vector<Point> &p) {
if (l >= r)
return inf;
if (r - l + 1 == 2)
return dist(p[l], p[r]);
int m = (l + r) / 2;
double min_left = solve(l, m, p);
double min_right = solve(m + 1, r, p);
double d = min(min_left, min_right);
d = min(d, solve_median(m, d, l, r, p));
return d;
}
int main() {
ifstream cin("cmap.in");
ofstream cout("cmap.out");
int n;
cin >> n;
vector<Point> p(n);
for (int i = 0; i < n; ++i)
cin >> p[i].x >> p[i].y;
sort(p.begin(), p.end(), [](const Point &A, const Point &B) -> bool {
return A.x < B.x;
});
double ans = solve(0, n - 1, p);
cout << fixed << setprecision(6) << ans << "\n";
return 0;
}