#include <cstdio> #include <cmath> #include <vector> #include <algorithm> struct P { double x, y; }; bool cmp(P a, P b) { return a.x < b.x; }; double sqr(double n) { return n * n; } double dis(P a, P b) { return sqr(a.x - b.x) + sqr(a.y - b.y); } int main() { int n; while (scanf("%d", &n) && n) { P p[10000]; for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y); if (n == 1) { puts("INFINITY"); continue; } std::sort(p, p + n, cmp); double min = dis(p[0], p[1]); for (int i = 0; i < n; i++) for (int j = i + 1; j < n && sqr(p[j].x - p[i].x) < min; j++) if (dis(p[j], p[i]) < min) min = dis(p[j], p[i]); min = sqrt(min); if (min > 10000.0 || fabs(min - 10000.0) < 0.00001) puts("INFINITY"); else printf("%.4lf\n", min); } return 0; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2013年1月30日
UVa 10245 - The Closest Pair Problem
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言