Pagini recente » Cod sursa (job #941009) | Cod sursa (job #128001) | Monitorul de evaluare | Diferente pentru utilizator/raresegay intre reviziile 4 si 3 | Cod sursa (job #2298940)
#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));
}
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]));
return ans;
}
int mij=(st+dr)/2;
ll best=minim(solve(st,mij),solve(mij+1,dr));
merge(y.begin()+st,y.begin()+mij,y.begin()+mij,y.begin()+dr,Z.begin());
copy(Z.begin(),Z.begin()+(dr-st),y.begin()+st);
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,a,b;
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;
}