Pagini recente » Cod sursa (job #780208) | Cod sursa (job #87665) | Cod sursa (job #220786) | Cod sursa (job #2290493) | Cod sursa (job #528167)
Cod sursa(job #528167)
#include <algorithm>
#include <cmath>
using namespace std;
#define INF (1ll<<60)
#define DIM 100005
#define sc second
#define fs first
#define LIM 8
pair <int,int> v[DIM];
int ind[DIM];
int n,m;
void read ()
{
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
scanf ("%d%d",&v[i].fs,&v[i].sc);
}
inline long long dist (pair <int,int> a,pair <int,int> b)
{
return 1LL*(a.fs-b.fs)*(a.fs-b.fs)+1LL*(a.sc-b.sc)*(a.sc-b.sc);
}
struct cmp
{
bool operator () (const int &a,const int &b)
{
return v[a].sc<v[b].sc;
}
};
long long calc (int st,int dr)
{
long long dst;
int mij,i,j;
if (dr-st<=2)
{
dst=INF;
for (i=st; i<dr; ++i)
for (j=i+1; j<=dr; ++j)
dst=min (dst,dist (v[i],v[j]));
return dst;
}
mij=(st+dr)/2; dst=min (calc (st,mij),calc (mij+1,dr));
m=0;
for (i=st; i<=dr; ++i)
if (abs (v[i].sc-v[mij].sc)<=dst)
ind[++m]=i;
sort (ind+1,ind+m+1,cmp ());
for (i=1; i<m; ++i)
for (j=i+1; j<=m && j-i<LIM; ++j)
dst=min (dst,dist (v[ind[i]],v[ind[j]]));
return dst;
}
int main ()
{
freopen ("cmap.in","r",stdin);
freopen ("cmap.out","w",stdout);
read ();
printf ("%.6lf",sqrt (calc (1,n)));
return 0;
}