Pagini recente » Cod sursa (job #2881682) | Cod sursa (job #1629871) | Cod sursa (job #3131493) | Cod sursa (job #98218) | Cod sursa (job #2772266)
#include <bits/stdc++.h>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
#define cin f
#define cout g
#define int long long
const int Max = 1e5 + 1;
void nos()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
namespace GeometryClosestPoints{
#define puncte vector<pair < int , int > >
int dist(pair < int , int > p1, pair < int , int > p2)
{
//patratul distantei
return (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}
puncte v;
int CPrec(int left, int right,puncte &x,puncte &y)
{
if(left >= right - 1)
return LLONG_MAX;
if(right - left == 2){
if(y[left] > y[left+1])
swap(y[left],y[left + 1]);
return dist(x[left],x[left + 1]);
}
int mid = (left + right) / 2;
int best = min(CPrec(left,mid,x,y),CPrec(mid,right,x,y));
merge(y.begin()+left,y.begin() + mid,y.begin() + mid,y.begin() + right,v.begin());
copy(v.begin(),v.begin() + (right - left),y.begin() + left);
int vpoint = 0;
for(int i = left; i<right;++i)
if(abs(y[i].second - x[mid].first) <= best)
v[vpoint++] = y[i];
for(int i = 0;i<vpoint;++i)
for(int j = i + 1;j<vpoint and j-i < 8;++j)
best = min(best,dist(v[i],v[j]));
return best;
}
long double ClosestPoints(puncte points)
{
sort(points.begin(), points.end());
puncte y(points.size());
for(int i=0;i<points.size();++i)
y[i] = {points[i].second,points[i].first};
v.resize(points.size() + 1);
return sqrt(CPrec(0,points.size(),points,y));
}
}
int n;
vector < pair < int , int > > a;
void read()
{
f>>n;
for(int i=1;i<=n;i++)
{
int x,y;
f>>x>>y;
a.push_back({x,y});
}
}
void solve()
{
g<<fixed<<setprecision(6)<<GeometryClosestPoints::ClosestPoints(a);
}
void restart()
{
}
int32_t main()
{
nos();
read();
solve();
restart();
return 0;
}