Pagini recente » Cod sursa (job #1972995) | Cod sursa (job #100111) | Cod sursa (job #2033405) | Cod sursa (job #795454) | Cod sursa (job #1026919)
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <fstream>
using namespace std;
const int NMAX = 100002;
class point {
public:
long long x, y;
} V[NMAX];
void keepMinim(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 divideConquer(int start, int final) {
if (start >= final)
return 1 << 30;
if (start + 1 == final)
return dist(V[start], V[final]);
int med = (start + final) / 2;
double result = 1 << 30;
keepMinim(result, divideConquer(start, med));
keepMinim(result, divideConquer(med + 1, final));
point tmp[10100];
int i, j, cnt = 0, contor;
for (i = med; i >= start; --i)
if (V[med].x - V[i].x <= result)
tmp[++cnt] = V[i];
for (i = med + 1; i <= final; ++i)
if (V[i].x - V[med].x <= result)
tmp[++cnt] = V[i];
sort(tmp + 1, tmp + cnt + 1, sortY);
for (i = 1; i <= cnt; ++i)
for (j = i + 1, contor = 1; j <= cnt && contor <= 6; ++j, ++contor)
keepMinim(result, dist(tmp[i], tmp[j]));
return result;
}
int main() {
ifstream in("cmap.in");
freopen("cmap.out", "w", stdout);
int N;
in >> N;
for (int i = 1; i <= N; ++i)
in >> V[i].x>>V[i].y;
sort(V + 1, V + N + 1, sortX);
double dist = divideConquer(1, N);
printf("%.6lf\n", dist);
return 0;
}