Pagini recente » Cod sursa (job #806820) | Cod sursa (job #2052465) | Cod sursa (job #253971) | Cod sursa (job #1822792) | Cod sursa (job #2711887)
#include <fstream>
#define mF "cmap"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
#include <complex>
#define x real
#define y imag
#define m (i+j>>1)
const int N = 100000;
struct P: public std::complex<double> {bool operator < (P p) {return x() == p.x()? y() < p.y(): x() < p.x();}} V[N], A[N];
double I(int i, int j)
{
int l = i, p = i, q = m; while (p < m and q < j)
if (V[p] < V[q]) A[l++] = V[p++]; else A[l++] = V[q++];
while (p < m) A[l++] = V[p++]; while (q < j) A[l++] = V[q++];
for (; i < j; i++) V[i] = A[i];
}
double R(int i, int j)
{
switch (j - i) {case 1: return .8e9; case 2: return I(i, j), abs(V[i] - V[i+1]);}
double r = R(i, m); r = std::min(r, R(m, j)); I(i, j);
for (int p = i; p < j; p++) if (abs(V[p].y() - V[m].y()) < r)
for (int q = p+1; q < p+8; q++) r = std::min(r, abs(V[p] - V[q]));
return r;
}
#include <iomanip>
int main()
{
int n; in >> n; for (int i = 0; i < n; i++) {int e; in >> e; V[i].x(e); in >> e; V[i].y(e);}
out << std::fixed << std::setprecision(7) << R(0, n);
}