Pagini recente » Cod sursa (job #1708098) | Profil M@2Te4i | Cod sursa (job #1794080) | Istoria paginii utilizator/tudorsavu | Cod sursa (job #1761008)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int NMax = 100000;
const long long oo = 1LL << 60;
pair <int, int> P[NMax + 5];
pair <int, int> Q[NMax + 5];
int N;
void Read()
{
fin >> N;
for(int i = 1; i <= N; i++)
{
fin>> P[i].first>>P[i].second;
}
sort(P+1,P+N+1);
}
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 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 Min1 = DEI(Left, Mid);
long long Min2 = DEI(Mid + 1, Right);
long long Min = min(Min1,Min2);
int k = 0;
for(int i = Left; i <= Right; ++i)
{
if(Dist(P[i],P[Mid]) < Min)
Q[++k] = P[i];
}
for(int i = 1; i <= k; i++)
for(int j = i+1; j <= k; j++)
Min = min(Min, Dist(P[i],P[j]));
return Min;
}
void Print()
{
fout << fixed << setprecision(6) << sqrt(DEI(1,N));
}
int main()
{
Read();
Print();
return 0;
}