Pagini recente » Cod sursa (job #3165737) | Cod sursa (job #2205516) | Cod sursa (job #2352138) | Cod sursa (job #63382) | Cod sursa (job #1495236)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const long long oo = 100000000000000LL;
const int NMax = 100005;
pair <long long, long long> P[NMax],Q[NMax];
int N;
long long Dist(pair<long long, long long> A, pair<long long, long long> B)
{
return (A.first-B.first)*(A.first-B.first) + (A.second-B.second)*(A.second-B.second);
}
long long DEI(int Left, int Right)
{
if(Left==Right)
return oo;
if (Right-Left==1)
return Dist(P[Left], P[Right]);
int Mid = (Left + Right) / 2;
long long A = DEI (Left, Mid);
long long B = DEI (Mid+1, Right);
long long Min = min(A,B);
int k = 0;
for(int i = Left; i<=Right; i++)
if(abs(P[i].first-P[Mid].first)<=Min)
Q[++k] = make_pair(P[i].second, P[i].first);
sort(Q+1,Q+k+1);
for(int i = 1; i<=k ; i++)
for(int j = i+1; j<=k && (j<=i+8) ; j++)
Min = min(Min,Dist(Q[i],Q[j]));
return Min;
}
int main()
{
fin>>N;
for(int i=1; i<=N; i++)
fin>>P[i].first>>P[i].second;
sort(P+1,P+N+1);
fout<<fixed<<setprecision(7)<<sqrt(DEI(1,N))<<"\n";
return 0;
}