Pagini recente » Cod sursa (job #2984089) | Cod sursa (job #1252972) | Cod sursa (job #3039098) | Istoria paginii runda/lmk_12_vs | Cod sursa (job #3256768)
#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=LLONG_MAX;
ll ans;
ll n;
struct point
{
ll x,y;
} v[100005];
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(int l,int r)
{
if(l==r)
return;
int mij=(l+r)/2;
ll xmid=v[mij].x;
solve(l,mij);
solve(mij+1,r);
vector<point> vec;
for(int i=l;i<=r;i++)
if((v[i].x-xmid)*(v[i].x-xmid)<ans)
vec.push_back(v[i]);
sort(vec.begin(),vec.end(),byy);
for(int i=0;i<vec.size();i++)
for(int j=i+1;j<vec.size();j++)
{
if((vec[i].y-vec[j].y)*(vec[i].y-vec[j].y)>=ans)
break;
ans=min(ans,dist(vec[i],vec[j]));
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fin>>n;
for(int i=1;i<=n;i++)
{
int x,y;
fin>>x>>y;
v[i]={x,y};
}
ans=INF;
solve(1,n);
ld rez=ld(sqrtl(ans));
fout<<fixed<<setprecision(12)<<rez;
return 0;
}