算法导论 · 分治法 · 最近点对问题
算法说明先将坐标系中的点按横坐标的大小进行排序,从中位数大小位置开始分割,独立的求两边的最短距离,去最小值,之后以这个中位线处往两边扩展最小值个长度,求改范围的最小值,比较三者,得出问题的最小值。对于求两边的最小值问题,递归调用。源代码#include <iostream>#include <cmath>#include <ctime>#incl...
·
- 算法说明
先将坐标系中的点按横坐标的大小进行排序,从中位数大小位置开始分割,独立的求两边的最短距离,去最小值,之后以这个中位线处往两边扩展最小值个长度,求改范围的最小值,比较三者,得出问题的最小值。对于求两边的最小值问题,递归调用。 - 源代码
#include <iostream>
#include <cmath>
#include <ctime>
#include <vector>
#include <algorithm>
using namespace std;
struct point { //坐标点
int x, y;
point(int xx, int yy) {
x = xx;
y = yy;
}
};
#define here(a) printf("here %d\n", a);
#define ptf printf("\n");
vector<point> p;
bool cmp(point a, point b); //比较函数,sort中使用
double minDistance(double a, double b); //返回a与b中最小的一个
double twoPointDistance(point a, point b); //计算两个点的距离
double closestPoint(int n, int m); //求最近点对
int main(int argc, char* argv[]) {
//input
freopen("cloestPointInput.txt", "r", stdin);
int n, x, y; //n对点对
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d%d", &x, &y);
p.push_back(point(x, y));
}
// //随机生成点对
// int n, x, y; //n对点对
// scanf("%d", &n);
// srand((unsigned)time(0));
// for(int i = 0; i < n; i++) { //随机生成坐标
// x = rand() % 100;
// y = rand() % 100;
// p.push_back(point(x, y));
// for(int j = 0; j < i; j++) {
// if(i > 0 && p[i].x == p[j].x && p[i].y == p[j].y) {
// //坐标去重
// i--;
// p.pop_back();
// break;
// }
// }
// }
//打印原始点对
for(int i = 0; i < p.size(); i++) {
printf("(%d,%d)\n", p[i].x, p[i].y);
}
//process
sort(p.begin(), p.end(), cmp); //排序
double min = closestPoint(0, n); //获取最近点对的距离
//output
freopen("cloestPointOutput.txt", "w", stdout);
printf("TwoPointMinDistance = %.2f", min);
return 0;
}
bool cmp(point a, point b) {
//比较函数,sort中使用
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
double minDistance(double a, double b) {
//返回a与b中最小的一个
if(a < b) return a;
return b;
}
double twoPointDistance(point a, point b) {
//计算两个点的距离
return sqrt(fabs(a.x - b.x) * fabs(a.x - b.x) + fabs(a.y - b.y) * fabs(a.y - b.y));
}
double closestPoint(int n, int m) {
//求最近点对
if(m - n == 2) return twoPointDistance(p[n], p[n + 1]); //子问题刚好是2个点
if(m - n == 3) { //子问题刚好是3个点
double b1 = twoPointDistance(p[n], p[n + 1]);
double b2 = twoPointDistance(p[n], p[n + 2]);
double b3 = twoPointDistance(p[n + 1], p[n + 2]);
b2 = min(b1, b2);
b3 = min(b2, b3);
return b3;
}
// here(1);
int mid = (n + m) / 2; //划分子问题,求出子问题的最短距离
double d1 = closestPoint(n, mid); //左闭右开
double d2 = closestPoint(mid, m);
double dm = minDistance(d1, d2); //获取最短的距离
// printf("d1 = %f d2 = %f dm = %f\n", d1, d2, dm);
//从区间中向两边扩展
int l = n, r = m - 1;
while(p[mid].x - dm > p[l].x && l <= m) l++;
while(p[mid].x + dm < p[r].x && r >= n) r--;
double temp;
for(int i = l; i < r; i++) {
if(p[i + 1].y - p[i].y > dm) continue;
else {
temp = twoPointDistance(p[i], p[i + 1]);
dm = min(temp, dm);
}
}
return dm;
}
- 输入数据
- 运行结果
更多推荐
已为社区贡献8条内容
所有评论(0)