算法设计课第三周（分治2 求最近平面点对问题 C++ 102行）

本文主要是介绍算法设计课第三周（分治2 求最近平面点对问题 C++ 102行），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实验3 求平面最小点距算法设计

思路和伪代码参考：【4.4分治最近点对问题】

一、【实验目的】

（1）熟悉分治算法的基本思想；

（2）理解分治算法改进的基本方法；

（3）理解不同情况下的算法时间复杂度的分析方法。

二、【实验内容】

平面上有n个点P1、P2、…Pi、…、Pn，n>1, Pi的坐标为（Xi,Yi）。请设计两种算法求距离最近的两个点及两者之间的距离，并分析算法的时间复杂度。

要求测试时，点的个数不能少于10个。

三、实验源代码

暴力法

#include <bits/stdc++.h>
using namespace std;int minAns = 999999;struct node
{int x;int y;
}a[12];int main()
{int n;cin>>n;int x1, y1, x2, y2;for(int i=0;i<n;i++){cin>>a[i].x>>a[i].y;}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i == j)continue;int nowAns = (int)sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));if(nowAns < minAns){minAns = min(minAns, nowAns);x1 = a[i].x, y1 = a[i].y;x2 = a[j].x, y2 = a[j].y;}}}cout << "The closest two points: " << '\n' << x1 << ' ' << y1 << '\n' << x2 << ' ' << y2 << endl;cout << minAns <<endl;
}/*
11
2 5
4 2
5 6
7 3
9 0
1 2
1 3
3 8
0 4
7 7
6 9
*/

【运行结果】

分治法

102行，哪用什么new几个指针数组。😂两个数组搞定了，用L, R划分好区间就行

#include <bits/stdc++.h> // 引入头文件，包含了常用的C++库函数
using namespace std; // 使用标准命名空间int minAns = 999999; // 初始化最小距离为一个较大的值
int n; // 定义点的数量
int nowAns, dotx1, dotx2, doty1, doty2; // 定义当前距离和点的坐标，用于输出struct node{ // 定义结构体node，表示一个点int x; // 点的x坐标int y; // 点的y坐标
}a[12]; // 定义一个结构体数组，存储输入的点bool compareX(node dot1, node dot2){ // 比较两个点的x坐标大小return dot1.x < dot2.x;
}bool compareY(node dot1, node dot2){ // 比较两个点的y坐标大小return dot1.y < dot2.y;
}int getDistance(int x1, int y1, int x2, int y2){ // 计算两点之间的距离return (int)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}int MinDistance(node a[], int size, int l, int r) // 递归函数，求解给定点集a中的最短距离
{	if(size == 3)//3个点{for(int i=0; i<2; i++){for(int j=i+1; j<=2; j++){nowAns = getDistance(a[i].x, a[i].y, a[j].x, a[j].y); // 计算两点之间的距离if(nowAns < minAns) // 如果当前距离小于最小距离{minAns = min(minAns, nowAns); // 更新最小距离dotx1 = a[i].x, doty1 = a[i].y; // 更新最近的两个点的坐标dotx2 = a[j].x, doty2 = a[j].y;}}	}return minAns; // 返回最小距离}else if(size == 2)//2个点直接算{nowAns = getDistance(a[l].x, a[l].y, a[r].x, a[r].y); // 计算两点之间的距离return nowAns; // 返回距离值}else if(size == 1)//只有一个点{cout << "Only one point!" << endl; // 输出提示信息return -1; // 返回-1表示错误}else{sort(a, a+size, compareX); // 按照x坐标对点进行排序int mid = (a[l].x + a[r].x) / 2; // 计算中间位置//分治，类似二分的分割int d1 = MinDistance(a, size/2, 0, mid); // 递归求解左半部分的最小距离int d2 = MinDistance(a, size/2, mid, size-1); // 递归求解右半部分的最小距离minAns = min(d1, d2); // //求δ,取左右两部分的最小值作为结果//取(mid-minAns, mid)，(mid, mid+minAns)区间，按y大小排序，选出x轴上下（最多）8个点int Xstart = mid - minAns;int Xend = mid + minAns;vector<node> v; // 定义一个结构体向量，用于存储在区间内的点for (int i = l; i <= r; i++){if(a[i].x > Xstart && a[i].x < Xend) // 如果点在区间内v.push_back(a[i]); // 将点加入向量}sort(v.begin(), v.end(), compareY); // 按照y坐标对点进行排序//从新排序好的数组中提取Xstart，Xend中所有的点for(int i=0; i<v.size(); i++){node point1 = v[i]; // 取出一个点for(int j=i+1; j<v.size(); j++){node point2 = v[j]; // 取出另一个点if(getDistance(v[i].x, v[i].y, v[j].x, v[j].y) < minAns) // 如果两点之间的距离小于最小距离{minAns = getDistance(v[i].x, v[i].y, v[j].x, v[j].y); // 更新最小距离dotx1 = point1.x, doty1 = point1.y; // 更新最近的两个点的坐标dotx2 = point2.x, doty2 = point2.y;}	}}}return minAns; // 返回最小距离
}int main() // 主函数
{cin>>n; // 输入点的数量for(int i=0;i<n;i++) // 循环输入每个点的坐标{cin>>a[i].x>>a[i].y;}MinDistance(a, n, 0, 10); // 调用递归函数求解最小距离cout << "The closest two points: " << '\n' << dotx1 << ' ' << doty1 << '\n' << dotx2 << ' ' << doty2 << endl; // 输出最近的两个点的坐标cout <<	minAns << endl; // 输出最小距离
}
/*
11
2 5
4 2
5 6
7 3
9 0
1 2
1 3
3 8
0 4
7 7
6 9
*/