C++利用分治算法编程实现最近点对问题

最近点对问题是指在平面上给定n个点，求其中距离最近的两个点之间的距离。

分治算法思路如下：

1. 将点按照x坐标排序，递归地将点集分成左右两部分。

2. 对于左右两个子集，分别递归求解最近点对问题。

3. 计算跨越左右两部分的最近点对，这个最近点对必然是左右两个子集中最近点对的其中一个。

4. 返回三个最近点对中的最小值。

代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

struct point {
double x, y;
};

bool cmp(point a, point b) {
return a.x < b.x;
}

double dist(point a, point b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}

double brute_force(vector<point>& a, int left, int right) {
double min_dist = 1e9;
for (int i = left; i <= right; i++) {
for (int j = i + 1; j <= right; j++) {
min_dist = min(min_dist, dist(a[i], a[j]));
}
}
return min_dist;
}

double closest_pair(vector<point>& a, int left, int right) {
if (left == right) {
return 1e9;
}
if (left + 1 == right) {
return dist(a[left], a[right]);
}
int mid = (left + right) >> 1;
double d = min(closest_pair(a, left, mid), closest_pair(a, mid + 1, right));
vector<point> strip;
for (int i = left; i <= right; i++) {
if (abs(a[i].x - a[mid].x) < d) {
strip.push_back(a[i]);
}
}
sort(strip.begin(), strip.end(), [](point a, point b) {
return a.y < b.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> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y;
}
sort(a.begin(), a.end(), cmp);
cout << closest_pair(a, 0, n - 1) << endl;
return 0;
}