Pagini recente » Cod sursa (job #1145985) | Cod sursa (job #422043) | Cod sursa (job #1145424) | Cod sursa (job #615196) | Cod sursa (job #2921414)
#include <bits/stdc++.h>
using namespace std;
int n;
pair <int,int> v[100001],inv[100001],vec[100001];
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 solve(int st,int dr)
{
if(dr-st==1)
return dist(v[st],v[st+1]);
if(dr-st==2)
return min(min(dist(v[st],v[st+1]),dist(v[st+1],v[st+2])),dist(v[st],v[st+2]));
int mij=(st+dr)/2;
long long delta=min(solve(st,mij),solve(mij+1,dr));
sort(inv+st,inv+dr+1);
int cnt=0;
for(int i=st;i<=dr;i++)
if(inv[i].second>=v[mij].first-delta&&inv[i].second<=v[mij].first+delta)
vec[++cnt]=inv[i];
for(int i=1;i<=cnt;i++)
for(int j=i+1;j<=min(i+5,cnt);j++)
delta=min(delta,dist(vec[i],vec[j]));
return delta;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
int i;
cin>>n;
for(i=1;i<=n;i++)
cin>>v[i].first>>v[i].second;
sort(v+1,v+n+1);
for(i=1;i<=n;i++)
inv[i]={v[i].second,v[i].first};
cout<<fixed<<setprecision(8)<<sqrt(solve(1,n));
return 0;
}