Pagini recente » Cod sursa (job #903129) | Istoria paginii utilizator/ifrim_andreea_carmen_322cb | Cod sursa (job #281013) | Cod sursa (job #597850) | Cod sursa (job #1305018)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define Nmax 100005
#define INF (1LL<<61)
using namespace std;
pair < long long, long long > x[Nmax],y[Nmax],Aux[Nmax];
int n;
inline long long Dist(pair < long long, long long > a, pair < long long, long long > b)
{
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
inline long long Solve(int l, int r)
{
if(l>=r) return INF;
if(r-l==1)
{
if(y[l]>y[l+1]) swap(y[l],y[l+1]);
return Dist(x[l],x[l+1]);
}
int mid=((l+r)>>1),len=0,i,j;
long long d;
d=min(Solve(l,mid),Solve(mid+1,r));
merge(y+l,y+mid+1,y+mid+1,y+r+1,Aux+1);
copy(Aux+1,Aux+(r-l+2),y+l);
for(i=l;i<=r;++i)
if(abs(x[mid].first-y[i].second)<=d) Aux[++len]=y[i];
for(i=1;i<len;++i)
for(j=i+1;j<=len && j<=i+5;++j)
d=min(d,Dist(Aux[i],Aux[j]));
return d;
}
int main()
{
int i;
freopen ("cmap.in","r",stdin);
freopen ("cmap.out","w",stdout);
scanf("%d", &n);
for(i=1;i<=n;++i) scanf("%lld%lld", &x[i].first,&x[i].second);
sort(x+1,x+n+1);
for(i=1;i<=n;++i) y[i]=make_pair(x[i].second,x[i].first);
printf("%.10lf\n", sqrt(1.0*Solve(1,n)));
return 0;
}