1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
|
#include<algorithm> #include<cmath> #define N 10000 #define MAX 10000 using namespace std;
struct { double x, y; double getLen(const Point& a) { return sqrt((a.x - x)*(a.x - x) + (a.y - y)*(a.y - y)); }
}point[N];
double DnC(int L, int R); int main() { int n, i; while (scanf("%d", &n) && n) { for (i = 0; i < n; i++) scanf("%lf%lf", &point[i].x, &point[i].y);
sort(point, point + n, [](const Point& a, const Point& b)->bool{return a.x < b.x; });
double ans = DnC(0, n - 1);
if (ans == 10000) puts("INFINITY"); else printf("%.4lfn", ans);
}
return 0; } double DnC(int L, int R) { int i, j; if (L >= R) return MAX; else if (R - L < 3) { double d = MAX; for (i = L; i < R; i++) for (j = i + 1; j <= R; j++) d = min(d, point[i].getLen(point[j])); return d; }
int M = (L + R) / 2;
double d = min(DnC(L, M), DnC(M + 1, R)); if (d == 0) return 0;
int n = 0; Point strip[N]; for (i = M; i >= L&&point[M].x - point[i].x < d; i--) strip[n++] = point[i]; for (i = M + 1; i <= R&&point[i].x - point[M].x < d; i++) strip[n++] = point[i];
sort(strip, strip + n, [](const Point& a, const Point& b)->bool{return a.y < b.y; });
for (i = 0; i < n; i++) for (j = 1; j <= 3 && i + j < n; j++) d = min(d, strip[i].getLen(strip[i + j]));
return d; }
|
近期评论