Pagini recente » Cod sursa (job #2376706) | Cod sursa (job #374978) | Cod sursa (job #1890627) | Clasament new | Cod sursa (job #1624490)
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct eu{long long x,y;};
eu v[100001];
long long i,j,n,m,k;
double minim=100000000;
bool sorting (eu a,eu b)
{
return a.x<b.x;
}
double dist(eu a,eu b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void divide(long long st,long long dr)
{
long long l1,l2,mid,i,j;
if(dr-st<=2)
{
for(i=st;i<dr;i++)
for(j=i+1;j<=dr;j++)
{
double x;
x=dist(v[i],v[j]);
if(x<minim)
minim=x;
}
}
else
{
mid=(dr+st)/2;
divide(st,mid);
divide(mid+1,dr);
long long a=1;
long long k=max(a,mid-4),k1=min(mid+4,n);
for(i=k;i<k1;i++)
for(j=i+1;j<=k1;j++)
{
double x;
x=dist(v[i],v[j]);
if(x<minim)
minim=x;
}
}
}
int main ()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%lld",&n);
for(i=1;i<=n;i++)
scanf("%lld%lld",&v[i].x,&v[i].y);
sort(v+1,v+n+1,sorting);
divide(1,n);
printf("%.6lf",minim);
return 0;
}