Pagini recente » Cod sursa (job #303343) | Cod sursa (job #2206507) | Cod sursa (job #426294) | Cod sursa (job #1344490) | Cod sursa (job #2299175)
#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;
int n;
vector<pair<ll,ll> > x;
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=min(ans,calc(x[i],x[j]));
return ans;
}
int mij=(st+dr)/2;
ll best=min(solve(st,mij),solve(mij+1,dr));
vector<pair<int,int> > aux;
for(int i=st;i<=dr;++i)
if(best>=abs(x[i].first-x[mij].first))
aux.push_back(x[i]);
int counter=aux.size();
sort(aux.begin(),aux.end(), [](auto &left, auto &right) {
return left.second < right.second;
});
for(int i=0;i<counter-1;++i)
for(int j=i+1;j<counter&&(j-i<8);++j)
best=min(calc(aux[i],aux[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());
cout<<fixed<<setprecision(6)<<sqrt(solve(1,n));
return 0;
}