Pagini recente » Cod sursa (job #598053) | Cod sursa (job #272862) | Cod sursa (job #305817) | Cod sursa (job #1099) | Cod sursa (job #1110259)
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<climits>
using namespace std;
int n,nry;
struct punct
{
long long x,y;
}v[100001],py[100001];
ifstream fin("cmap.in");
ofstream fout("cmap.out");
void citire()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
}
int cmp(punct a,punct b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
inline long long dist(punct a,punct b)
{
return (a.x-b.x)*(a.x-b.x)*1LL+(a.y-b.y)*(a.y-b.y)*1LL;
}
int cmp2(punct a,punct b)
{
return a.y<b.y;
}
long long imparte(int p,int u)
{
long long dmin=LLONG_MAX;
int mij;
if(u-p+1<=3)
{
for(int i=p;i<u;i++)
for(int j=i+1;j<=u;j++)
dmin=min(dmin,dist(v[i],v[j]));
return dmin;
}
mij=(p+u)/2;
dmin=min(imparte(p,mij),imparte(mij+1,u));
nry=0;
for(int i=mij+1;i<=u && v[i].y-v[mij].y<dmin;i++)
{
py[++nry].x=v[i].x;
py[nry].y=v[i].y;
}
for(int i=mij;i>=p && v[mij].y-v[i].y<dmin;i--)
{
py[++nry].x=v[i].x;
py[nry].y=v[i].y;
}
sort(py+1,py+nry+1,cmp2);
for(int i=1;i<=nry;i++)
{
for(int j=i+1;j<=nry && j<=i+8;j++)
{
dmin=min(dmin,dist(py[i],py[j]));
}
}
return dmin;
}
int main()
{
citire();
sort(v+1,v+n+1,cmp);
fout<<setprecision(6)<<fixed<<sqrt(imparte(1,n));
return 0;
}