Pagini recente » Cod sursa (job #1716969) | Cod sursa (job #3148154) | Cod sursa (job #2104053) | Cod sursa (job #18405) | Cod sursa (job #1184390)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int NMAX = 100010;
const long long INF = (1LL << 60);
int N;
pair<int, int> X[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(X + Left, X + Right);
return Dist(X[Left], X[Left + 1]);
}
int Mid = (Left + Right) / 2;
long long CrtD = min(Cmap(Left, Mid), Cmap(Mid, Right));
merge(X + Left, X + Mid, X + Mid, X + Right, Aux);
copy(Aux, Aux + Right - Left, X + Left);
int x = X[Mid].first;
int K = 0;
for(int i = Left; i < Right; ++ i)
if(abs(x - X[i].first) <= CrtD)
Aux[++ K] = X[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("%d %d", &X[i].first, &X[i].second);
printf("%.8lf\n", 1.0*sqrt(Cmap(0, N)));
return 0;
}