Pagini recente » Cod sursa (job #563310) | Cod sursa (job #2216623) | Cod sursa (job #3208099) | Cod sursa (job #2623217) | Cod sursa (job #1662835)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const int N = 100000;
const long long INF = 2000000000000000000LL;
const double eps = 0.000001;
struct punct
{
int x, y;
};
ifstream in("cmap.in");
ofstream out("cmap.out");
punct v[N], aux[N];
int n;
void citire()
{
in >> n;
for (int i = 0; i < n; i++)
in >> v[i].x >> v[i].y;
in.close();
}
bool cmp(punct p, punct q)
{
return p.x < q.x;
}
long long min(long long a, long long b)
{
return a < b ? a : b;
}
long long distanta(punct p1, punct p2)
{
return (long long)(p1.x - p2.x) * (p1.x - p2.x) + (long long)(p1.y - p2.y) * (p1.y - p2.y);
}
int modul(int x)
{
return x < 0 ? -x : x;
}
long long calcul(int st, int dr, long long d)
{
int nr, m = (st + dr) / 2, i, j, k, lim;
punct mij = v[m];
i = k = st;
j = m + 1;
while (i <= m && j <= dr)
if (v[i].y <= v[j].y)
aux[k++] = v[i++];
else
aux[k++] = v[j++];
while (i <= m)
aux[k++] = v[i++];
while (j <= dr)
aux[k++] = v[j++];
nr = 0;
for (i = st; i <= dr; i++)
{
v[i] = aux[i];
if (modul(v[i].x - mij.x) <= d)
aux[nr++] = aux[i];
}
for (i = 0; i + 1 < nr; i++)
{
lim = i + 8;
if (lim > nr)
lim = nr;
for (j = i + 1; j < lim; j++)
d = min(d, distanta(aux[i], aux[j]));
}
return d;
}
long long apropiate(int st, int dr)
{
if (st == dr)
return INF;
int m = (st + dr) / 2;
long long r1, r2, r;
r1 = apropiate(st, m);
r2 = apropiate(m + 1, dr);
r = min(r1, r2);
return calcul(st, dr, r);
}
int main()
{
citire();
sort(v, v + n, cmp);
out << fixed << setprecision(6) << sqrt(apropiate(0, n - 1)) << "\n";
out.close();
return 0;
}