Pagini recente » Cod sursa (job #756619) | Cod sursa (job #2178235) | Cod sursa (job #1993589) | Cod sursa (job #1218263) | Cod sursa (job #1236170)
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int MAX=100005;
const long long INF=1ll<<60;
struct punct
{
int x,y;
}v[MAX];
int y[MAX],aux[MAX];
bool cmp(punct i,punct j)
{
return i.x<j.x;
}
long long dist(int i,int j)
{
return 1ll*(v[i].x-v[j].x)*(v[i].x-v[j].x)+1ll*(v[i].y-v[j].y)*(v[i].y-v[j].y);
}
long long divide_impera(int st,int dr)
{
long long ds,dd;
if(st==dr)
return INF;
if(st+1==dr)
{
if(v[y[st]].y>v[y[dr]].y)
y[st]=dr,y[dr]=st;
return dist(st,dr);
}
int mj=(st+dr)/2;
ds=divide_impera(st,mj);
dd=divide_impera(mj+1,dr);
if(dd<ds)ds=dd;
int i=st,j=mj+1,k=0;
while(i<=mj and j<=dr)
if(v[y[i]].y<v[y[j]].y)
aux[++k]=y[i++];
else
aux[++k]=y[j++];
while(i<=mj)aux[++k]=y[i++];
while(j<=dr)aux[++k]=y[j++];
for(i=st;i<=dr;++i)
y[i]=aux[i-st+1];
k=0;
for(i=st;i<=dr;++i)
if(abs(v[i].x-v[mj].x)<=ds)
aux[++k]=i;
for(i=1;i<=k-7;++i)
for(j=i+1;j<=i+7;++j)
if(ds>dist(i,j))
ds=dist(i,j);
return ds;
}
int main()
{
int n,i;
fin>>n;
for(i=1;i<=n;++i)
{
fin>>v[i].x>>v[i].y;
y[i]=i;
}
sort(v+1,v+n+1,cmp);
fout.precision(6);
fout<<fixed<<sqrt((double)divide_impera(1,n));
return 0;
}