Pagini recente » Cod sursa (job #786093) | Cod sursa (job #488268) | Cod sursa (job #110539) | Cod sursa (job #64263) | Cod sursa (job #2921418)
#include <bits/stdc++.h>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
int n;
pair <int,int> v[100001],inv[100001],vec[100001];
double dist(pair <int,int> a,pair<int,int> b)
{
return sqrt(1LL*(a.first-b.first)*(a.first-b.first)+1LL*(a.second-b.second)*(a.second-b.second));
}
double 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;
double 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+2,cnt);j++)
delta=min(delta,dist(vec[i],vec[j]));
return delta;
}
int main()
{
int i;
in>>n;
for(i=1;i<=n;i++)
in>>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};
out<<fixed<<setprecision(8)<<solve(1,n);
return 0;
}