Pagini recente » Cod sursa (job #954036) | Cod sursa (job #3257269) | Cod sursa (job #266315) | Cod sursa (job #2930139) | Cod sursa (job #1139641)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 100010;
const long long int INF = 1LL << 60;
int N, K;
pair<int, int> X[NMAX], Y[NMAX], Aux[NMAX];
long long Dist(pair<int, int> A, pair<int, int> B)
{
return 1LL * (A.first - B.first) * (A.first - B.first) + 1LL * (A.second - B.second) * (A.second - B.second);
}
long long Cmap(int Left, int Right)
{
if(Left >= Right - 1) return INF;
if(Right - Left == 2)
{
sort(Y + Left, Y + Right);
return Dist(Y[Left], Y[Left + 1]);
}
int Mid = (Left + Right) / 2;
long long CrtD = min(Cmap(Left, Mid), Cmap(Mid, Right));
merge(Y + Left, Y + Mid, Y + Mid, Y + Right, Aux);
copy(Aux, Aux + Right - Left, Y + Left);
K = 0;
for(int i = Left; i < Right; ++ i)
if(abs(X[Mid].first - Y[i].second) <= CrtD)
Aux[++ K] = Y[i];
for(int i = 1; i <= K; ++ i)
for(int j = i + 1; j <= K && j - i < 8; ++ j)
CrtD = min(CrtD, Dist(Aux[i], Aux[j]));
return CrtD;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
scanf("%i", &N);
for(int i = 0; i < N; ++ i) scanf("%i %i", &X[i].first, &X[i].second);
sort(X, X + N);
for(int i = 0; i < N; ++ i) Y[i] = make_pair(X[i].second, X[i].first);
printf("%.6lf\n", sqrt(1.0 * Cmap(0, N)));
}