Pagini recente » Cod sursa (job #2665148) | Cod sursa (job #2958533) | Cod sursa (job #3196140) | Cod sursa (job #3256230) | Cod sursa (job #1379414)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#define NMAX 100005
#define LINF ~(1LL<<63)
#define i64 long long
using namespace std;
int n;
pair<i64,i64> X[NMAX],Y[NMAX],v[NMAX];
void read()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%lld%lld",&X[i].first,&X[i].second);
sort(X,X+n);
for(int i=0;i<n;++i)
{
Y[i].second=X[i].first;
Y[i].first=X[i].second;
}
}
inline i64 dist(const pair<i64,i64> a,const pair<i64,i64> b)
{
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
i64 cmap(int st,int dr)
{
if(dr-st<=1)
return LINF;
if(dr-st==2)
{
if(Y[st]>Y[st+1])
swap(Y[st],Y[st+1]);
return dist(X[st],X[st+1]);
}
int mid=st+(dr-st)/2;
i64 best=min(cmap(st,mid),cmap(mid,dr));
int v_size=0;
for(int i=st;i<dr;++i)
if(abs(Y[i].second-X[mid].first<=best))
v[++v_size]=Y[i];
for(int i=0;i<v_size;++i)
for(int j=i+1;j<=v_size&&j-i<8;++j)
best=min(best,dist(v[i],v[j]));
return best;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
read();
i64 d=cmap(0,n);
double Ans=sqrt((double)d);
printf("%lf",Ans);
}