Pagini recente » Cod sursa (job #2566869) | Cod sursa (job #1042) | Cod sursa (job #2119887) | Cod sursa (job #1246489) | Cod sursa (job #1412824)
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
#define x first
#define y second
#define NMAX 100005
#define p(x,y) make_pair(x,y)
#define ULL unsigned long long
#define pairi pair <ULL,ULL>
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
ULL x,y;
pairi v[NMAX],aux[NMAX];
inline ULL dist(pairi A, pairi B)
{
ULL r=1LL*(A.x-B.x)*(A.x-B.x)+1LL*(A.y-B.y)*(A.y-B.y);
return r;
}
void interclas(int st, int mij, int dr)
{
int i,j,k=st;
for (i=st,j=mij+1;i<=mij && j<=dr;)
if (v[i].y<v[j].y) aux[k++]=v[i++];
else aux[k++]=v[j++];
for (;i<=mij;++i) aux[k++]=v[i];
for (;j<=dr;++j) aux[k++]=v[j];
for (i=st;i<=dr;++i)
v[i]=aux[i];
}
ULL distmin(int st, int dr)
{
if (st+1==dr)
{
interclas(st,st,dr);
return dist(v[st],v[dr]);
}
if (st+2==dr)
{
interclas(st,st,st+1);
ULL q=dist(v[st],v[st+1]);
q=min(q,dist(v[st+1],v[dr]));
interclas(st,st+1,dr);
return q;
}
int mij=(st+dr)>>1;
ULL q1=distmin(st,mij);
ULL q2=distmin(mij+1,dr);
interclas(st,mij,dr);
ULL minim=min(q1,q2);
for (int i=st;i<dr;++i)
for (int j=i+1;j<=i+7 && j<=dr;++j)
minim=min(minim,dist(v[i],v[j]));
return minim;
}
int main()
{
int i;
fin>>n;
for (i=1;i<=n;++i)
{
fin>>x>>y;
v[i]=p(x,y);
}
fout<<setprecision(6)<<fixed<<sqrt((double)distmin(1,n))<<"\n";
return 0;
}