Pagini recente » Cod sursa (job #2032272) | Cod sursa (job #2919809) | Cod sursa (job #2594541) | Cod sursa (job #430733) | Cod sursa (job #1234694)
#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[100005];
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)
{
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
{
int m=(p+u)/2;
double mn1=min1(divide(p,m),divide(m,u));
double mn2=mn1;
for(int i=m;i>=p && v[m].x-v[i].x<=mn1;i--)
for(int 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;
}