河工大分治法求最近点对问题

最近点对问题是计算平面上一组点中距离最近的两个点的问题。分治法求解最近点对问题的基本思路是将点集按照 x 坐标排序，然后递归地将点集分成两个子集，直到每个子集中只有一个点。然后合并两个子集的结果，找到跨越两个子集的最近点对。

具体而言，可以按照以下步骤进行：

1. 将点集按照 x 坐标排序，将点集分成两个子集。

2. 递归地对两个子集分别求最近点对。

3. 取两个子集的最近点对中距离最小的那个点对作为当前的最近点对。

4. 查找跨越两个子集的可能更小的最近点对。具体而言，可以按照 y 坐标从小到大的顺序遍历所有与中线距离小于当前最小距离的点，计算它们与它们后面的 7 个点的距离，并更新最小距离。

5. 返回当前的最近点对。

时间复杂度为 O(n log n)。

相关问题

C语言分治法求最近点对问题代码

以下是C语言分治法求最近点对问题的代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define INF 1e20 //定义无穷大

//定义点的结构体
typedef struct {
double x;
double y;
} Point;

//比较函数，按x坐标排序
int cmp_x(const void *a, const void *b) {
Point *p1 = (Point *)a;
Point *p2 = (Point *)b;
if (p1->x < p2->x) return -1;
else if (p1->x > p2->x) return 1;
else return 0;
}

//比较函数，按y坐标排序
int cmp_y(const void *a, const void *b) {
Point *p1 = (Point *)a;
Point *p2 = (Point *)b;
if (p1->y < p2->y) return -1;
else if (p1->y > p2->y) return 1;
else return 0;
}

//计算两点之间的距离
double dist(Point p1, Point p2) {
return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

//暴力求解最近点对
double brute_force(Point *p, int n) {
double min_dist = INF;
for (int i = 0; i < n-1; i++) {
for (int j = i+1; j < n; j++) {
double d = dist(p[i], p[j]);
if (d < min_dist) min_dist = d;
}
}
return min_dist;
}

//合并最近点对
double merge(Point *p, int n, double d) {
double mid = p[n/2].x; //中线
Point *strip = (Point *)malloc(n * sizeof(Point));
int j = 0;
for (int i = 0; i < n; i++) {
if (fabs(p[i].x - mid) < d) strip[j++] = p[i];
}
qsort(strip, j, sizeof(Point), cmp_y); //按y坐标排序
double min_dist = d;
for (int i = 0; i < j-1; i++) {
for (int k = i+1; k < j && strip[k].y-strip[i].y < min_dist; k++) {
double d = dist(strip[i], strip[k]);
if (d < min_dist) min_dist = d;
}
}
free(strip);
return min_dist;
}

//分治求解最近点对
double closest_pair(Point *p, int n) {
if (n <= 3) return brute_force(p, n);
int mid = n/2;
double dl = closest_pair(p, mid); //左半边最近点对距离
double dr = closest_pair(p+mid, n-mid); //右半边最近点对距离
double d = fmin(dl, dr); //取左右半边最近点对距离的较小值
return merge(p, n, d); //合并最近点对
}

int main() {
int n;
printf("请输入点的数量：");
scanf("%d", &n);
Point *p = (Point *)malloc(n * sizeof(Point));
printf("请输入%d个点的坐标：\n", n);
for (int i = 0; i < n; i++) {
scanf("%lf%lf", &p[i].x, &p[i].y);
}
qsort(p, n, sizeof(Point), cmp_x); //按x坐标排序
double ans = closest_pair(p, n);
printf("最近点对的距离为：%lf\n", ans);
free(p);
return 0;
}

c++实现分治法求最近点对问题

最近点对问题是指在平面上给定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;
}