Pagini recente » Cod sursa (job #1579451) | Cod sursa (job #1945534) | Cod sursa (job #1945529) | Cod sursa (job #2644428) | Cod sursa (job #1275363)
#include<fstream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#define inf 1LL<<61
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct pct{
long long x;
long long y;
}x[100010],y[100010],z[100100];
int n,i,j;
int cmp(pct a,pct b) {
return a.x<b.x;
}
long long lg(pct a,pct b) {
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline long long minim(long long a,long long b) {
if(a<b)
return a;
return b;
}
void intercl(long long st,long long mid,long long dr) {
long long i=st,j=mid+1,k=0;
while(i<=mid&&j<=dr)
if(x[i].x<=x[j].x)
y[++k]=x[i++];
else
y[++k]=x[j++];
for(;i<=mid;i++)
y[++k]=x[i];
for(;j<=dr;j++)
y[++k]=x[j];
for(i=st;i<=dr;i++)
x[i]=y[i-st+1];
}
long long sol(long long st, long long dr) {
long long mid,r,i,j,k;
if(st==dr)
return inf;
if(st+1==dr){
intercl(st,st,dr);
return lg(x[st],x[dr]);
}
mid=(st+dr)/2;
r=minim(sol(st,mid),sol(mid+1,dr));
intercl(st,mid,dr);
k=0;
for(i=st;i<=dr;i++)
if(x[mid].x-x[i].x<=r&&x[i].x-x[mid].x<=r)
z[++k]=x[i];
for(i=1;i<=k;i++)
for(j=1;j<=7&&j+i<=k;j++)
r=minim(r,lg(z[i],z[i+j]));
return r;
}
int main (){
f>>n;
for(i=1;i<=n;i++)
f>>x[i].x>>x[i].y;
sort(x+1,x+n+1,cmp);
g<<setprecision(6)<<fixed<<sqrt(sol(1,n));
return 0;
}