Pagini recente » Cod sursa (job #1834920) | Cod sursa (job #3273498) | Cod sursa (job #1854171) | Cod sursa (job #919545) | Cod sursa (job #1662836)
#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;
}