分治法 解 平面最接近点对问题

  • V2_258965
    了解作者
  • 1.7KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-05-26 04:14
    上传日期
C++ 课程教师给的代码,用于解决平面最接近点问题
分治法 解 平面最接近点对问题.rar
  • 分治1.cpp
    4.8KB
内容介绍
//来自http://bricks.blog.edu.cn/user2/bricks/archives/2006/1288329.shtml #include<string.h> #include<stdio.h> #include<math.h> #define MAX 10240 // 点的个数 struct Node{ double x, y; int p; }; Node a[MAX], tem[MAX]; double Dist( Node &u, Node &v ) { // 计算点u 和v之间的距离 double dx = u.x-v.x; double dy = u.y-v.y; return sqrt( dx * dx + dy * dy ); } bool cmpx(Node a, Node b) { return a.x > b.x; // 如果a.x > b.x 返回,交换ab } bool cmpy(Node a, Node b) { return a.y > b.y; // 如果a.x > b.x 返回,交换ab } void MergeSort(int from, int to, Node *a, Node *tmp, bool cmp(Node, Node)) { if(to - from == 1) return; if(to - from == 2) { if(cmp(a[from], a[from+1]) == true) { Node t = a[from]; a[from] = a[from+1]; a[from+1] = t; } return; } int mid = (to + from) >> 1; MergeSort(from, mid, a, tmp, cmp); MergeSort(mid, to, a, tmp, cmp); int p1 = mid - from - 1, p2 = to - mid - 1, p = to - from; while(p1 >= 0 && p2 >= 0) { if(cmp(a[from + p1] , a[mid + p2]) == true) // 前面的大 tmp[--p] = a[from + p1--]; else tmp[--p] = a[mid + p2--]; } while(p1 >= 0) tmp[--p] = a[from + p1--]; while(p2 >= 0) tmp[--p] = a[mid + p2--]; memcpy(&a[from], tmp, (to-from)*sizeof(Node)); return; } void close( Node *X, Node *Y, Node *Z, int l, int r, Node &a, Node &b, double &d ) { // 计算最近点对 // X[l:r] 按x坐标排序 // Y[l:r] 按y坐标排序 if (r-l == 1) { a = X[l]; b = X[r]; d = Dist( X[l], X[r] ); return ; } if (r-l == 2) { double d1 = Dist( X[l], X[l+1] ); double d2 = Dist( X[l+1], X[r] ); double d3 = Dist( X[l], X[r] ); if (d1 <= d2 && d1 <= d3) { a = X[l]; b = X[l+1]; d = d1; return ; } if (d2 <= d3) { a = X[l+1]; b = X[r]; d = d2; }else{ a = X[l]; b = X[r]; d = d3; } return ; } int m = (l+r)/2; // 在Z[l:m] 和Z[m+1:r]中创建按y排序的表 int f = l; // Z[l:m]的游标 int g = m+1; // Z[m+1:r]的游标 for (int i = l; i <= r; i++) { if (Y[i].p > m) Z[g++] = Y[i]; else Z[f++] = Y[i]; } close( X, Z, Y, l, m, a, b, d ); double dr; Node ar, br; close( X, Z, Y, m+1, r, ar, br, dr ); if (dr < d) { a = ar; b = br; d = dr; } // 重构Y f = l, g = m+1; int k = l; while (f <= m && g <= r) { if (Z[f].y > Z[g].y) Y[k++] = Z[g++]; else Y[k++] = Z[f++]; } if (f > m) for (;g <= r;g ++ ) Y[k++] = Z[g]; else for (;f <= m;f ++ ) Y[k++] = Z[f]; // 距离小于d的点放入Z k = l; // Z的游标 for (int i = l; i <= r; i++) if (fabs(Y[m].x - Y[i].x) < d) Z[k++] = Y[i]; // 通过检查Z[ l : k-1 ]中的所有点对,寻找较近的点对 for (int i = l; i < k; i++){ for (int j = i+1; j < k && Z[j].y - Z[i].y < d;j ++ ) { float dp = Dist( Z[i], Z[j] ); if (dp < d) { d = dp; a = X[Z[i].p]; b = X[Z[j].p]; } } } return ; } bool Closest( Node X[], int n, Node &a, Node &b, double &d ) { // 输入:点集X[],和点的个数n,数组从0开始 // 如果少于2个点,则返回 false // 否则,返最近的距离和对应的两个点a,b if (n < 2) return false; MergeSort( 0, n, X, tem, cmpx ); // 按x坐标排序 Node Y[MAX]; for (int i = 0; i < n; i++) { Y[i].p = i; Y[i].x = X[i].x; Y[i].y = X[i].y; } MergeSort( 0, n, Y, tem, cmpy ); // 按y坐标排序 Node Z[MAX]; close( X, Y, Z, 0, n-1, a, b, d ); return true; } int main() { Node X[MAX], a, b; int n; double d; while (scanf("\n%d",&n) !=EOF && n != 0) { for (int i = 0;i < n;i ++ ) scanf("\n%lf %lf",&X[i].x, &X[i].y); if (Closest( X, n, a, b, d )) printf("%lf %lf %lf %lf %lf\n",a.x, a.y, b.x, b.y, d); else printf("error!\n"); } return(0); }
评论
    相关推荐
    • C++ Primer
      C++经典教程,其内容是C++大师Stanley B. Lippman丰富的实践经验和C++标准委员会原负责人Josée Lajoie对C++标准深入理解的完美结合,已经帮助全球无数程序员学会了C++。 对C++基本概念和技术全面而且权威的阐述,对...
    • c++课件
      c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件
    • C++ PRrimer
      本书是久负盛名的C++经典教程,其内容是C++大师Stanley B. Lippman丰富的实践经验和C++标准委员会原负责人Josée Lajoie对C++标准深入理解的完美结合,已经帮助全球无数程序员学会了C++。本版对前一版进行了彻底的...
    • C++
      C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++
    • C++ primer
      本文档具有C++ primer 以及 C++ primer 标准答案各一份,内容清晰充实!希望与热爱C++的学友们一起同舟共济,努力学习!
    • c++information
      c++c++c++c++c++c++c++c++c++c++c++c++
    • c++yuyanbiancheng
      这是C和C++集成的编程环境!这是C和C++集成的编程环境!这是C和C++集成的编程环境!这是C和C++集成的编程环境!这是C和C++集成的编程环境!
    • effective C++
      有关C++编程方面的检验性介绍,对由C转向C++,和有C++编程基础的程序员有帮助,不过是英文版
    • C++ Primer
      这本处适合各个阶段的C++程序员,这本书可以帮助初学者快速入门,里面有最实用,最容易理解的代码;同时这也是有经验的C++程序员最好的一本参考手册
    • C++ Primer
      本书是久负盛名的C++经典教程引,其内容是C++大师Stanley B. Lippman丰富的实践经验和C++标准委员会原负责人Josée Lajoie对C++标准深入理解的完美结合,已经帮助全球无数程序员学会了C++