ConsoleApplication17.zip

// ConsoleApplication17.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 #include <math.h> #include <random> #include <iostream> #include <time.h> using namespace std; struct point//定义结构体 { int Point;//点的的下标 float x, y;//点的坐标x，y }; float a1[100000] = {0};//初始化数组a1 float b1[100000] = {0};//初始化数组b1 float Distance(point A, point B)//计算两点间距离 { return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y) * (A.y - B.y)); } void quickSort(float *arr, float *arr2, int L, int H)//快速排序 { float temp = arr[L]; float temp2 = arr2[L];//选定中轴数 int i = L;int j = H; if (L < H) { while (i < j) { while (i<j && arr[j] > temp)//数组中从右往左查找第一个比中轴数小的数 j--; arr[i] = arr[j]; arr2[i] = arr2[j]; while (i < j && arr[i] <= temp)//从左往右查找 i++; arr[j] = arr[i]; arr2[j] = arr2[i]; } arr[i] = temp; arr2[i] = temp2; quickSort(arr, arr2, L, i - 1);//递归 quickSort(arr, arr2, i + 1, H);} else return; } void cloest(point X[], point Y[], int l, int h, point &a, point &b, float &min)//分治法查找最近的点 { int i = 0, j = 0, mid = 0; point al, ar, bl, br; float ml = 0, mr = 0; if (h - l <= 0)//当输入点数小于等于1时 { cout << "请输入大于1的整数"; } else if ((h - l) == 1) //点数等于2时直接求距离 { min = Distance(X[l], X[h]); } else { if ((h - l) == 2) //当点数等于3时直接求最短距离 { ml = Distance(X[l], X[l + 1]);//求出1 2点距离 mr = Distance(X[l], X[l + 2]);//求出1 3点距离 min = Distance(X[l + 1], X[l + 2]);//求出2 3点距离 if ((ml <= mr) && (ml <= min))//比较得出最短距离 {a = X[l];//更新点a b = X[l + 1];//更新点b min = ml;//更新min } else {if (mr <= min) {a = X[l]; b = X[l + 2]; min = mr;} else {a = X[l + 1]; b = X[l + 2]; } } } else//当点数大于3时 {mid = (h - l) / 2 + l;//作中垂线 point *PL = new point[(h - l) / 2 + 1];//将平面分为左右均等的两部分点集 point *PR = new point[(h - l) / 2 + 1]; j = 0;int number = 0; for (i = 0; i <= h - l; i++) {if (Y[i].Point <= mid)//记录左边的点 {PL[j++] = Y[i];} else { PR[number++] = Y[i];// 记录右边的点 } } cloest(X, PL, l, mid, al, bl, ml); // 递归计算求得左点集的最近点 cloest(X, PR, mid + 1, h, ar, br, mr);// 递归计算求得右点集的最近点 if (ml < mr)//比较左右点集最短距离 {a = al;//更新点a b = bl;//更新点b min = ml;//更新最短距离min }else {a = ar; b = br; min = mr; } point *Temp = new point[h - l + 1];//定义点集Temp用于记录窄缝中的点 number = 0; for (i = 0; i <= h - l; i++) //记录距离中垂线距离小于min的点，保存到点集 { if ((X[mid].x - Y[i].x) < min || ((Y[i].x - X[mid].x) < min))//判断与中垂线距离是否小于min { Temp[number].x = Y[i].x; Temp[number++].y = Y[i].y; } } for (i = 0; i < number; i++)//计算窄缝中是否有点距小于min的点对 { for (j = i + 1; (j < (i + 7)) && (j < number); j++)//y坐标已排序，只需向下遍历6个点即可 { ml = Distance(Temp[i], Temp[j]); if (ml < min) //与min比较 { a = Temp[i];//更新点a b = Temp[j];//更新点b min = ml;//更新min } } } delete[]Temp;//删除点集Temp } } } void Init(point P1[], point P2[], int N) {std::default_random_engine rand;//生成随机不重复点对 for (int i = 0; i < N; i++) { a1[i] = rand()*0.0000001;//随机生成x坐标 b1[i] = rand()*0.0000001;//随机生成y坐标 //cout << a1[i] <<","<< b1[i] <<endl; } quickSort(a1,b1,0, N - 1);//对点对的横坐标快速排序 for (int i = 0; i < N; i++) { P1[i].x = a1[i];//储存在结构体P1中 P1[i].y = b1[i]; } quickSort(b1, a1, 0, N - 1);//对点对的纵坐标快速排序 for (int i = 0; i < N; i++) { P2[i].Point = i; P2[i].x = b1[i];//储存在结构体P2中 P2[i].y = a1[i]; } } void baoliqiujie(point P1[], point P2[], int N)//暴力求解，与分治求解结果作比较 { float D = 10000; for (int x = 0; x < N; x++) { for (int y = 1; y < N; y++) { float E = Distance(P1[y], P1[x]);//求每个点之间的距离 if (E < D&&E != 0) { D = E;//取最小值 } } }cout << "暴力求解得到的最近距离：" << D << endl;//输出暴力求解结果 } float main() { int n; cout << "输入点的个数n(n>1)："; cin >> n;//输入点对数 point A, B; float MIN = 0; point *X = new point[n];//定义点集X point *Y = new point[n];//定义点击Y clock_t start, finish;//计时 start = clock();//计时开始 Init(X, Y, n); //生成点对并排序 cloest(X,Y,0,n-1,A,B,MIN);//求最近点对 finish = clock();//计时结束 baoliqiujie(X, Y, n);//暴力求解 float t; t = float(finish - start) / CLOCKS_PER_SEC; cout<<"采用分治算法用时："<< t; //输出算法运算时间 cout <<"平面最近的两个点为：("<< A.x <<","<< A.y <<")"<<"("<< B.x <<","<< B.y <<")\n两点距离为："<<MIN;//输出最近点对及其距离 system("pause"); }