Pagini recente » Cod sursa (job #2480425) | Cod sursa (job #2896533) | Cod sursa (job #1128993) | Cod sursa (job #2397009) | Cod sursa (job #956260)
Cod sursa(job #956260)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
struct point {
int x, y;
} x[100100];
void chmin(double &A, double B) {
if (A - B > 0.000000001)
A = B;
}
bool sortX(point A, point B) {
return A.x < B.x;
}
bool sortY(point A, point B) {
return A.y < B.y;
}
double dist(point A, point B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
double solve(int left, int right) {
if (left >= right)
return 1 << 30;
if (left + 1 == right)
return dist(x[left], x[right]);
int med = (left + right) / 2;
double res = 1 << 30;
chmin(res, solve(left, med));
chmin(res, solve(med + 1, right));
point tmp[10100];
int i, j, cnt = 0, used;
for (i = med; i >= left; --i)
if (x[med].x - x[i].x <= res)
tmp[++cnt] = x[i];
for (i = med + 1; i <= right; ++i)
if (x[i].x - x[med].x <= res)
tmp[++cnt] = x[i];
sort(tmp + 1, tmp + cnt + 1, sortY);
for (i = 1; i <= cnt; ++i)
for (j = i + 1, used = 1; j <= cnt && used <= 6; ++j, ++used)
chmin(res, dist(tmp[i], tmp[j]));
return res;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
//while (1) {
int N;
scanf("%d", &N);
// if (N == 0)
// return 0;
for (int i = 1; i <= N; ++i)
scanf("%d%d", &x[i].x, &x[i].y);
sort(x + 1, x + N + 1, sortX);
double dist = solve(1, N);
printf("%.6lf\n", dist);
//}
return 0;
}