Pagini recente » Cod sursa (job #2543931) | Cod sursa (job #87415) | Cod sursa (job #2032880) | Cod sursa (job #2222526) | Cod sursa (job #2380374)
#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;
int s[100005];
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));
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[i]=r++;
else
s[i]=l++;
}
for(int i=st;i<dr;++i){
for(int j=i+1;j<=min(dr,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;
}