Pagini recente » Cod sursa (job #1722399) | Cod sursa (job #846229) | Cod sursa (job #2906456) | Cod sursa (job #2122442) | Cod sursa (job #2765566)
#include<bits/stdc++.h>
#define dim 100//002
#define int long long
using namespace std;
ifstream fin ("cmap.in");
ofstream fout("cmap.out");
struct el
{
int x,y;
}v[dim],w[dim];
inline bool cmp (const el &a1,const el &a2)
{
if (a1.x==a2.x)
return a1.y<a2.y;
return a1.x<a2.x;
}
inline bool cmp2 (const el &a1,const el &a2)
{
if (a1.y==a2.y)
return a1.x<a2.x;
return a1.y<a2.y;
}
long double dist (int i,int j)
{
long double sol=(v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y);
sol=sqrt(sol);
return sol;
}
long double dist2 (int i,int j)
{
long double sol=(w[i].x-w[j].x)*(w[i].x-w[j].x)+(w[i].y-w[j].y)*(w[i].y-w[j].y);
sol=sqrt(sol);
return sol;
}
long double rez (int st,int dr)
{
if (st==dr)
return 1e17;
int nr=0,i,j,mij=(st+dr)/2;
long double s1=rez(st,mij),s2=rez(mij+1,dr);
long double s=min(s1,s2);
for (i=st;i<=dr;i++)
if (dist(mij,i)<=s)
w[++nr]=v[i];
sort(w+1,w+nr+1,cmp2);
for (i=1;i<=nr;i++)
for (j=i-1;j>=i-8&&j>=1;--j)
if (dist2(i,j)<s)
s=dist2(i,j);
return s;
}
int32_t main ()
{
int n,i;
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort (v+1,v+n+1,cmp);
/*long double p=dist(1,2);
for (i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
p=min(p,dist(i,j));*/
fout<<fixed<<setprecision(7)<<rez (1,n);
}