Pagini recente » Cod sursa (job #1485332) | Cod sursa (job #2087517) | Cod sursa (job #995828) | Cod sursa (job #1958368) | Cod sursa (job #1233052)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
using namespace std;
FILE *f=fopen("cmap.in","r");
FILE *g=fopen("cmap.out","w");
struct vec
{
int x,y;
}v[100001];
/*double mn(double a, double b)
{
if(a-b<1e-5)
return a;
else return b;
}*/
double dist(vec a, vec b) {
return sqrt((a.x-b.x) * (a.x-b.x) + (a.y - b.y) * (a.y - b.y));
}
int n,i;
bool cmp(vec i, vec j)
{
/*if(i.x==j.x)return i.y<j.y; else*/ return i.x<j.x;
}
/*double divide(int l, int r)
{
int m=(l+r)/2;
if(r==l+2)
{
return mn(dist(v[l],v[l+1]),dist(v[l+1],v[l+2]));
}
if(r==l+1)
{
return dist(v[l],v[l+1]);
} else return mn((divide(l,m)),divide(m+1,r));
}*/
double divide(int l, int r) {
if (r-l+1<= 3) {
return min(dist(v[l],v[l+1]), min(dist(v[l],v[l+2]), dist(v[l+1],v[l+2])));
} else {
int m=(l+r)/2;
double s=min(divide(l,m),divide(m,r)),s1;
s1=s;
for(int i=m;i>=l && v[m].x-v[i].x<=s;i--)
for (int j=1;j<=7 && i+j<=r;j++) {
s1= min(s1,dist(v[i],v[i+j]));
}
return s1;
}
}
int main()
{
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%d%d",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
fprintf(g,"%.6lf",divide(1,n));
fclose(g);
return 0;
}