Pagini recente » Cod sursa (job #169732) | Cod sursa (job #2630589) | Cod sursa (job #391885) | Cod sursa (job #2291442) | Cod sursa (job #2434153)
#include <bits/stdc++.h>
#define lld long long
#define nmax 100005
#define INF 9223372036854775806LL
using namespace std;
int n, x, y;
vector<pair<int,int>>xs, ys;
vector<pair<int,int>>v(nmax);
lld distance(pair<int,int> &a, pair<int,int> &b)
{
return 1LL*(a.first - b.first)*(a.first - b.first) + 1LL*(a.second - b.second)*(a.second - b.second);
}
lld minn(lld a, lld b)
{
if (a < b) return a;
return b;
}
lld di(int st, int dr)
{
if (st >= dr)
return INF;
if (dr - st == 1)
{
if (ys[st] > ys[st+1])
swap(ys[st],ys[st+1]);
return distance(xs[st], xs[st+1]);
}
int m = (st + dr)/2;
lld bst = minn(di(st, m-1),di(m,dr));
sort(ys.begin() + st, ys.begin() + dr + 1);
int sz = 0;
for (int i=st;i<=dr;++i)
if (abs(ys[i].second-xs[m].first)<=bst)
v[sz++] = ys[i];
for (int i=0;i<sz-1;++i)
for (int j=i+1;j<sz && j - i < 8;++j)
bst = minn(bst, distance(v[i],v[j]));
return bst;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&n);
xs.reserve(n);
ys.reserve(n);
for (int i=1;i<=n;++i)
{
scanf("%d %d",&x,&y);
xs.push_back(make_pair(x,y));
}
sort(xs.begin(), xs.end());
for (int i=0;i<xs.size();++i)
ys.push_back(make_pair(xs[i].second, xs[i].first));
lld ans = di(0,n-1);
cout<<setprecision(6)<<fixed<<sqrt(ans)<<'\n';
fclose(stdin);
fclose(stdout);
return 0;
}