Pagini recente » Cod sursa (job #223220) | Cod sursa (job #2494640) | Cod sursa (job #1582050) | Cod sursa (job #1543460) | Cod sursa (job #2380366)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
int n;
long long x,y;
vector <pair<long long,long long>> pct;
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);
}
long long cmap(int st, int dr){
if(dr-st+1<=3){
long long ret = 1e15;
for(int i=st;i<dr;++i)
for(int j=i+1;j<=dr;++j)
ret = min(ret, dist(pct[i],pct[j]));
return ret;
}
int mij = (st+dr)>>1;
long long ss = min(cmap(st,mij), cmap(mij+1,dr));
vector <int> s;
int l = st, r = mij+1;
for(int i=st;i<=dr;++i){
if(l == mij+1 || (r<=dr && pct[l].second<=pct[r].second))
s.push_back(r++);
else
s.push_back(l++);
}
for(int i=0;i<dr-st+1;++i){
for(int j=i+1;j<=min(dr-st,i+7);++j)
ss = min(ss,dist(pct[s[i]],pct[s[j]]));
}
return ss;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%lld%lld",&x,&y);
pct.push_back({x,y});
}
sort(pct.begin(),pct.end());
pct.push_back({0,0});
cout<<setprecision(7)<<fixed<<sqrt(cmap(0,n-1));
return 0;
}