首页 > 代码库 > 算法导论之最近顶点对
算法导论之最近顶点对
算法导论在计算几何学这章给出了最近顶点对的求法：采用典型的分治算法
（1）分解：将所有顶点按照x坐标排序后大致分为俩个大小相等的集合L和R
（2）求解：分别求出L和R集合中的最小具体，并取二者的较小值为当前的最小值ans
（3）合并：对于分属于两个集合的点，每次各取出一个点，计算两点的距离，每次与ans比较去较小值来更新ans的值，并且可以进行优化，具体的优化步骤一共有3个，具体见算法导论。
算法的运行时间为O（n log n),具体代码如下：
#include <cstdio>#include <algorithm>#include <cmath>using namespace std;int const MAX_N = 100005;struct Point{ double x, y;};Point p[MAX_N];int yy[MAX_N];bool cmpx(Point const& pa, Point const& pb){ return pa.x < pb.x;}bool cmpy(int const& a, int const& b){ return p[a].y < p[b].y;}inline double dis(Point const& pa, Point const& pb){ return sqrt((pa.x - pb.x) * (pa.x - pb.x) + (pa.y - pb.y) * (pa.y - pb.y));}inline double min(double const& a, double const& b){ return a < b ? a : b;}double closeset(int low, int high){ if(low + 1 == high) { return dis(p[low], p[high]); } if(low + 2 == high) { return min(dis(p[low], p[high]), min(dis(p[low], p[low + 1]), dis(p[low + 1], p[high]))); } int mid = (low + high) >> 1; double ans = min(closeset(low, mid), closeset(mid + 1, high)); int cnt = 0; for(int i = low; i <= high; i++) { if(p[i].x > p[mid].x - ans && p[i].x < p[mid].x + ans) { yy[cnt++] = i; } } sort(yy, yy + cnt, cmpy); for(int i = 0; i < cnt; i++) { int k = (i + 7) > cnt ? cnt : (i + 7); for(int j = i + 1; j < k; j++) { if(p[yy[j]].y - p[yy[j]].y >= ans) break; ans = min(ans, dis(p[yy[j]], p[yy[i]])); } } return ans;}int main(){ //freopen("min.txt", "r", stdin); int n, i; while(scanf("%d", &n) != EOF) { if(!n) break; for(i = 0; i < n; i++) { scanf("%lf %lf", &p[i].x, &p[i].y); } sort(p, p + n, cmpx); double ans = closeset(0, n - 1); printf("%.2lf\n", ans); } return 0;}
算法导论之最近顶点对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。