首页 > 代码库 > uva10245 - The Closest Pair Problem(暴力+剪枝)
uva10245 - The Closest Pair Problem(暴力+剪枝)
题目:uva10245 - The Closest Pair Problem(暴力+剪枝)
题目大意:给出N个点,求这些点中最小的两点距离。
解题思路:把这些点中两两之间的距离都算出来,这样的复杂度是O(n^2),会超时,所以加了一个减枝。
先将所有的点按照x坐标排序。然后在计算的过程中,如果发现要计算的这两点的X坐标之差的绝对值已经大于等于当前的最小值,那么说明后面的点计算距离一定比这个最小值要大。
这题的正解貌似是分治法,可惜没看懂。
代码:
#include <stdio.h> #include <algorithm> #include <stdlib.h> #include <math.h> using namespace std; const int MAXN = 10005; const double MLen = 10000; const double esp = 1e-9; struct NODE { double x, y; }node[MAXN]; int cmp (const NODE &a, const NODE &b) { return a.x < b.x; } double dist (int i, int j) { double px = fabs (node[i].x - node[j].x); double py = fabs (node[i].y - node[j].y); return sqrt (px * px + py * py); } int main () { int n; double minLen, d; while (scanf ("%d", &n) && n) { for (int i = 0; i < n; i++) scanf ("%lf%lf", &node[i].x, &node[i].y); sort (node, node + n, cmp); minLen = MLen; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // printf ("%lf %lf\n", node[j].x - node[i].x - minLen,esp); if (node[j].x - node[i].x - minLen >= -esp) break; d = dist(i, j); // printf (".4lf\n", d); if (d < minLen) minLen = d; } } // printf ("%.4lf\n", minLen); if (fabs (minLen - MLen) <= esp) printf ("INFINITY\n"); else printf ("%.4lf\n", minLen); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。