Pagini recente » Cod sursa (job #2352689) | Cod sursa (job #1844329) | Cod sursa (job #2661858) | Cod sursa (job #1803649) | Cod sursa (job #1624485)
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct eu{int x,y;};
eu v[100001];
int 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(int st,int dr)
{
int 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);
int k=max(1,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("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&v[i].x,&v[i].y);
sort(v+1,v+n+1,sorting);
divide(1,n);
printf("%.6lf",minim);
return 0;
}