Pagini recente » Cod sursa (job #2169072) | Cod sursa (job #839864) | Cod sursa (job #998040) | Cod sursa (job #2452871) | Cod sursa (job #3216098)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long long ll;
typedef long double ld;
const ll INF=1e18;
ll ans=INF;
ll n;
struct point
{
ll x,y;
} v[100005];
bool byx(point a, point b)
{
return a.x<b.x;
}
bool byy(point a, point b)
{
return a.y<b.y;
}
ll dist(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void solve(ll l,ll r)
{
if(l==r)
return;
if(l+1==r)
{
ans=min(ans,dist(v[l],v[r]));
return;
}
ll mij=(l+r)/2;
solve(l,mij);
solve(mij+1,r);
vector<point> vals;
for(ll i=l;i<=r;i++)
if((v[i].x-v[mij].x)*(v[i].x-v[mij].x)<ans)
vals.push_back(v[i]);
sort(vals.begin(),vals.end(),byy);
for(int i=0;i<vals.size();i++)
for(int j=i+1;j<vals.size();j++)
{
if((vals[j].y-vals[i].y)*(vals[j].y-vals[i].y)>=ans)
break;
ans=min(ans,dist(vals[i],vals[j]));
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,byx);
solve(1,n);
ld rez=ld(sqrt(ld(ans)));
fout<<fixed<<setprecision(10)<<rez;
return 0;
}