Pagini recente » Cod sursa (job #398232) | Cod sursa (job #915740) | Cod sursa (job #1181763) | Cod sursa (job #2283159) | Cod sursa (job #2926745)
/// Ispir Alexandru - O(n log^2 n)
#include <bits/stdc++.h>
const int NMAX = 2e5 + 5;
struct punct {
long double x, y;
};
int n;
std :: vector < punct > p(NMAX);
std :: ifstream fin("cmap.in");
std :: ofstream fout("cmap.out");
bool cmpX(punct a, punct b) {
if (a.x != b.x)
return (a.x < b.x);
return (a.y < b.y);
}
bool cmpY(punct a, punct b) {
if (a.y != b.y)
return (a.y < b.y);
return (a.x < b.x);
}
long double dist(punct a, punct b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
long double solve(int l, int r) {
if (r - l + 1 <= 3) {
long double Min = 9e18;
for (int i = l; i <= r; ++ i)
for (int j = i + 1; j <= r; ++ j)
Min = std :: min(Min, dist(p[i], p[j]));
return Min;
}
else {
int mid = ((l + r) >> 1);
long double Min = std :: min(solve(l, mid), solve(mid + 1, r));
std :: vector < punct > b;
for (int i = l; i <= r; ++ i)
if (abs(p[i].x - p[mid].x) <= Min)
b.push_back(p[i]);
std :: sort(b.begin(), b.end(), cmpY);
for (int i = 0; i < b.size(); ++ i)
for (int j = i + 1; j < std :: min(int(b.size()), i + 9); ++ j)
Min = std :: min(Min, dist(b[i], b[j]));
return Min;
}
}
int main() {
fin >> n;
for (int i = 0; i < n; ++ i)
fin >> p[i].x >> p[i].y;
std :: sort(p.begin(), p.begin() + n, cmpX);
fout << std :: fixed << std :: setprecision(8) << solve(0, n - 1);
return 0;
}