Pagini recente » Cod sursa (job #2184331) | Cod sursa (job #1670079) | Borderou de evaluare (job #1569054) | Cod sursa (job #2936814) | Cod sursa (job #1662368)
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
#define N 100001
#define INF 9223372036854775807
struct punct
{
int x, y;
};
int n;
punct v[N], aux[N];
inline bool compara(punct p1, punct p2)
{
return p1.x < p2.x;
}
inline long long minim(long long a, long long b)
{
return a < b ? a : b;
}
inline int modul(int x)
{
return x > 0 ? x : -x;
}
inline 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);
}
inline long long calcul(int st, int dr, long long d)
{
int nr = 0, m = (st + dr) >> 1, i, j, k;
i = st;
k = st;
j = m + 1;
punct mij = v[m];
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 = 1; i <= nr; i++)
{
int lim = i + 7;
if(lim > nr)
lim = nr;
for(j = i + 1; j <= lim; j++)
d = minim(d, distanta(aux[i], aux[j]));
}
return d;
}
long long divideEtImpera(int st, int dr)
{
if(st == dr)
return INF;
int m = (st + dr) >> 1;
long long d1, d2, d;
d1 = divideEtImpera(st, m);
d2 = divideEtImpera(m + 1, dr);
d = minim(d1, d2);
return calcul(st, dr, d);
}
int main()
{
in >> n;
for(int i = 1; i <= n; i++)
in >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, compara);
out << fixed << setprecision(6) << sqrt(divideEtImpera(1, n)) << '\n';
return 0;
}