c++实现分治法求最近点对问题
时间: 2023-11-26 18:20:48 浏览: 54
最近点对问题是指在平面上给定n个点,找出其中距离最近的两个点的距离。分治法是求解最近点对问题的经典算法之一。
1. 将所有点按照横坐标排序,然后分成左右两个子问题;
2. 对于左右两个子问题,分别递归求解最近点对;
3. 在左右两个子问题的最近点对中,选取距离更近的一对作为候选解;
4. 计算横跨左右两个子问题的点对的距离,并将它们按照纵坐标排序;
5. 在纵向排序后的点集中,依次计算每个点与后面最多7个点之间的距离,并选取距离更近的一对作为候选解;
6. 在步骤3和步骤5中选取距离更近的一对作为最终解。
下面是C++代码实现:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
struct Point {
int x;
int y;
};
bool cmp_x(Point a, Point b) {
return a.x < b.x;
}
bool cmp_y(Point a, Point b) {
return a.y < b.y;
}
double dist(Point a, Point b) {
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double brute_force(vector<Point>& points, int lo, int hi) {
double min_dist = 1e9;
for (int i = lo; i <= hi; i++) {
for (int j = i + 1; j <= hi; j++) {
min_dist = min(min_dist, dist(points[i], points[j]));
}
}
return min_dist;
}
double closest_pair(vector<Point>& points, int lo, int hi) {
if (lo == hi) {
return 1e9;
}
if (hi - lo == 1) {
return dist(points[lo], points[hi]);
}
int mid = (lo + hi) / 2;
double d1 = closest_pair(points, lo, mid);
double d2 = closest_pair(points, mid + 1, hi);
double d = min(d1, d2);
vector<Point> strip;
for (int i = lo; i <= hi; i++) {
if (abs(points[i].x - points[mid].x) < d) {
strip.push_back(points[i]);
}
}
sort(strip.begin(), strip.end(), cmp_y);
int n = strip.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n && strip[j].y - strip[i].y < d; j++) {
d = min(d, dist(strip[i], strip[j]));
}
}
return d;
}
int main() {
int n;
cin >> n;
vector<Point> points(n);
for (int i = 0; i < n; i++) {
cin >> points[i].x >> points[i].y;
}
sort(points.begin(), points.end(), cmp_x);
double ans = closest_pair(points, 0, n - 1);
if (ans < 1e9) {
cout << ans << endl;
} else {
cout << "No solution" << endl;
}
return 0;
}