Pagini recente » Cod sursa (job #2498066) | Cod sursa (job #922914) | Cod sursa (job #2269032) | Cod sursa (job #78718) | Cod sursa (job #1234693)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
FILE *f=fopen("cmap.in","r");
FILE *g=fopen("cmap.out","w");
struct nod{
double x;
double y;
}v[100001];
int i,n;
bool cmp(nod a, nod b){
if (a.x==b.x) return a.y<b.y ;else return a.x<b.x;
}
double dist(nod a, nod b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double min1(double a, double b)
{
if(a-b<1e-5) return a;
else return b;
}
double divide(int p,int u)
{
int m,i,j;
if (u-p+1<=3)
return min1(dist(v[p],v[p+1]),min1(dist(v[p],v[p+2]),dist(v[p+1],v[p+2])));
else
{
m=(p+u)/2;
double mn1=min1(divide(p,m),divide(m,u));
double mn2=mn1;
for(i=m;i>=p && v[m].x-v[i].x<=mn1;i--)
for(j=1;j<=7 && i+j<=u;j++)
mn2=min1(mn1,dist(v[i],v[i+j]));
return mn2;
}
}
int main()
{
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
fprintf(g,"%.6lf",divide(1,n));
fclose(g);
return 0;
}