Pagini recente » Cod sursa (job #2517746) | Cod sursa (job #2616120) | Cod sursa (job #2449337) | Cod sursa (job #2292472) | Cod sursa (job #2299122)
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
#define maxn 100005
#define ll long long
const ll inf=4e18;
#define minim(a,b) a<b?a:b
int n;
vector<pair<ll,ll> > x,y,Z(maxn);
ll calc(const pair<ll,ll> a,const pair<ll,ll> b){
return ((a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second));
}
void mergexd(int st,int mij,int dr){
vector<pair<int,int> > aux(dr-st+1);
int i,j,k=0;
for(i=dr-mij,j=st,k=0;j<mij&&i>=0;k++){
if(y[j]>y[dr-i]){
aux[k]=(y[dr-i]);--i;}
else if(y[j]<y[dr-i])
aux[k]=(y[j++]);
else if(y[j].second>y[dr-i].second){
aux[k]=(y[dr-i]);--i;}
else
aux[k]=(y[j++]);
}
while(j<mij)aux[k++]=y[j++];
while(i>=0)aux[k++]=y[dr-i],--i;
copy(aux.begin(),aux.begin()+(dr-st),y.begin()+st);
}
ll solve(int st,int dr)
{
if(dr-st<=3){
ll ans=inf;
for (int i=st;i<dr;i++)
for (int j=i+1;j<=dr;j++){
ans=minim(ans,calc(x[i],x[j]));
if(y[i]>y[i+1])
swap(y[i],y[i+1]);
}
return ans;
}
int mij=(st+dr)/2;
ll best=minim(solve(st,mij),solve(mij+1,dr));
mergexd(st,mij,dr);
int counter=0;
for(int i=st;i<=dr;++i)
if(best>=abs(y[i].second-x[mij].first))
Z[counter++]=y[i];
for(int i=0;i<counter-1;++i)
for(int j=i+1;j<counter&&j-i<8;++j)
best=minim(calc(Z[i],Z[j]),best);
return best;
}
int main()
{
int i;
cin>>n;
x.resize(n+1);
for(i=1;i<=n;i++)
cin>>x[i].first>>x[i].second;
sort(x.begin(),x.end());
y.resize(n+1);
for(i=1;i<=n;i++)
y[i]=make_pair(x[i].second,x[i].first);
cout<<fixed<<setprecision(6)<<sqrt(solve(1,n));
return 0;
}