Pagini recente » Cod sursa (job #3229652) | Cod sursa (job #2958629) | Cod sursa (job #2852716) | Cod sursa (job #2931335) | Cod sursa (job #3277370)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int nmax = 1e5;
int n;
pair<int,int> v[nmax + 5];
int rez = LLONG_MAX;
int dist(pair<int,int> a, pair<int,int> b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
void solve(int st, int dr)
{
if(st == dr)
{
return;
}
if(dr - st == 1)
{
rez = min(rez, dist(v[st], v[dr]));
return;
}
int mij = (st + dr) >> 1;
solve(st, mij);
solve(mij + 1, dr);
vector<pair<int,int>> p;
for(int i=st;i<=dr;i++)
{
if((v[i].first - v[mij].first) * (v[i].first - v[mij].first) < rez)
{
p.push_back(v[i]);
}
}
sort(p.begin(), p.end(), [](pair<int,int> a, pair<int,int> b){return a.second < b.second;});
for(int i=0;i<p.size();i++)
{
for(int j=i+1;j<p.size();j++)
{
if((v[j].second - v[i].second) * (v[j].second - v[i].second) >= rez)
{
break;
}
rez = min(rez, dist(v[i], v[j]));
}
}
}
signed main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i].first>>v[i].second;
}
sort(v + 1, v + n + 1);
solve(1, n);
long double rez_sq = sqrt(rez);
cout<<fixed<<setprecision(7);
cout<<rez_sq<<'\n';
return 0;
}