Pagini recente » Cod sursa (job #1582429) | Cod sursa (job #354838) | Cod sursa (job #1626446) | Cod sursa (job #270431) | Cod sursa (job #983860)
Cod sursa(job #983860)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define i64 long long
#define NMax 100005
#define oo 1LL<<60
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
pair <i64, i64> X[NMax],Array[NMax];
int N;
bool cmp(pair <i64, i64>A,pair <i64, i64>B)
{
return (B.second<A.second);
}
void Read()
{
fin>>N;
for(int i=1;i<=N;i++)
{
int x,y;
fin>>x>>y;
X[i]=make_pair(x,y);
}
sort(X+1,X+N+1);
}
inline i64 Dist(pair <i64,i64> A, pair <i64,i64>B)
{
return (B.first-A.first)*(B.first-A.first)+(B.second-A.second)*(B.second-A.second);
}
i64 DEI(int Left, int Right)
{
if(Left==Right)
return oo;
if(Right-Left==1)
{
return Dist(X[Left],X[Right]);
}
int Mid=(Left+Right)/2;
i64 a=DEI(Left,Mid);
i64 b=DEI(Mid+1,Right);
long long V=min(a,b);
int k=0;
for(int i=Left;i<=Right;i++)
{
if(X[i].first-X[Mid].first<=V)
{
Array[++k]=X[i];
}
}
sort(Array+1,Array+k+1,cmp);
for(int i=1;i<=k;i++)
for(int j=i+1;j<=i+8&&j<=k;j++)
V=min(V,Dist(Array[i],Array[j]));
return V;
}
void Print()
{
fout<<fixed<<setprecision(6)<<sqrt((double)DEI(1,N))<<'\n';
}
int main()
{
Read();
Print();
return 0;
}