Pagini recente » Cod sursa (job #2325735) | Cod sursa (job #149267) | Cod sursa (job #618004) | Cod sursa (job #2350275) | Cod sursa (job #2683097)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const ll NMAX = 100005;
const ll INF = 1000000000000000001;
pair <ll,ll> a[NMAX],b[NMAX],c[NMAX];
ll n;
ll Abs(ll x){
if(x<0) return -x;
return x;
}
ll dist(pair<ll,ll> x,pair<ll,ll> y){
return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second);
}
ll solve(ll st,ll dr){
if(st>=dr) return INF;
if(dr-st+1==2){
if(b[st+1]<b[st]){
pair<ll,ll> aux;
aux=b[st+1];
b[st+1]=b[st];
b[st]=aux;
}
return dist(a[st],a[st+1]);
}
ll mij=(st+dr)/2;
ll d=min(solve(st,mij),solve(mij+1,dr));
ll i=st,j=mij+1,m=0;
while(i<=mij and j<=dr){
if(b[i]<=b[j]){
c[++m]=b[i];
i++;
}
else{
c[++m]=b[j];
j++;
}
}
while(i<=mij){
c[++m]=b[i];
i++;
}
while(j<=dr){
c[++m]=b[j];
j++;
}
ll m2=0;
for(ll i=st;i<=dr;i++){
if(Abs(b[i].second-a[mij].first)<=d)
c[++m2]=b[i];
}
for(ll i=1;i<=m2;i++)
for(ll j=i+1;j<=m2 and j<=i+7;j++)
d=min(d,dist(c[i],c[j]));
return d;
}
int main()
{
fin >> n;
for(ll i=1;i<=n;i++) fin >> a[i].first >> a[i].second;
sort(a+1,a+n+1);
for(ll i=1;i<=n;i++){
b[i].first=a[i].second;
b[i].second=a[i].first;
}
fout << setprecision(6) << fixed << sqrt(solve(1,n));
return 0;
}