uva 10245 The Closest Pair Problem
题目大意：给出n个点，求出距离最近的两点间的距离。若点与点间的距离都大于10000，，输出INFINITY
解题思路：这题的正统做法是分治，偷懒方法是暴力加剪枝。先按x坐标排序，然后fabs(p[i] – p[j]) > ans的点就可以直接跳过了。
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>#include<math.h>using namespace std;struct point{double x, y;};double cal(double x1, double y1, double x2, double y2) {return sqrt((x2 – x1) * (x2 – x1) + (y2 – y1) * (y2 – y1));}point p[10005];int cmp(point a, point b) {return a.x < b.x;}int main() {int n;while (scanf("%d", &n), n) {for (int i = 0; i < n; i++) {scanf("%lf %lf", &p[i].x, &p[i].y);}sort(p, p + n, cmp);double ans = 0xFFFFFFF;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (fabs(p[i].x – p[j].x) – ans > 1e-9)break;double temp = cal(p[i].x, p[i].y, p[j].x, p[j].y);if (temp – ans < 1e-9) {ans = temp;}}}if (ans – 10000 < 0) {printf("%.4lf\n", ans);}else printf("INFINITY\n");}return 0;}
人生没有彩排，只有现场直播，所以每一件事都要努力做得最好
