Pagini recente » Cod sursa (job #2294736) | cv1101 | Cod sursa (job #1213648) | Cod sursa (job #2246931) | Cod sursa (job #2713749)
#include <fstream>
#define mF "cmap"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
const int N = 100000;
#include <complex>
#define x real
#define y imag
struct P: std::complex<double>
{inline bool operator < (P p) {return x() == p.x()? y() < p.y(): x() < p.x();}} V[N], O[N];
#define m (i+j>>1)
double R(int i, int j)
{
if (j - i == 1) return .5e10;
double r = R(i, m), l = V[m].x(); r = std::min(r, R(m, j));
int p = i, q = m, k = i; while (p < m and q < j)
O[k++] = V[p].y() < V[q].y()? V[p++]: V[q++];
while (p < m) O[k++] = V[p++]; while (q < j) O[k++] = V[q++];
for (p = i; p < j; p++) if (V[p] = O[p], abs(O[p].x() - l) < r)
for (q = p+1; q < p+7 and q < j; q++) r = std::min(r, abs(O[p] - O[q]));
return r;
}
#undef m
#include <algorithm>
#include <iomanip>
int main()
{
int n; in >> n; for (int i = 0; i < n; i++) {int a, b; in >> a >> b; V[i].x(a), V[i].y(b);}
std::sort(V, V + n); out << std::fixed << std::setprecision(7) << R(0, n);
}