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

分治算法实现最近点对问题：

1.将点集P按照x坐标排序，得到有序点集Px。

2.将点集P按照y坐标排序，得到有序点集Py。

3.递归地将Px分成两部分，分别处理左右两部分，得到最短距离d1。

4.在Py中，对于每个点p，只需要考虑y坐标与其相差不超过d1的点q，计算p与q的距离，取最小值d2。

5.取d1和d2中的最小值作为最终结果。

代码实现如下：

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

struct Point {
double x, 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) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx*dx + dy*dy);
}

double brute_force(Point p[], int n) {
double d = 1e9;
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
d = min(d, dist(p[i], p[j]));
}
}
return d;
}

double closest_pair(Point p[], int n) {
if (n == 2)
return dist(p[0], p[1]);
if (n <= 3)
return brute_force(p, n);
int mid = n / 2;
double midx = p[mid].x;
double d = min(closest_pair(p, mid), closest_pair(p+mid, n-mid));
Point strip[n];
int j = 0;
for (int i = 0; i < n; ++i) {
if (abs(p[i].x - midx) < d)
strip[j++] = p[i];
}
sort(strip, strip+j, cmp_y);
for (int i = 0; i < j; ++i) {
for (int k = i+1; k < j && strip[k].y - strip[i].y < d; ++k) {
d = min(d, dist(strip[i], strip[k]));
}
}
return d;
}

int main() {
int n;
cin >> n;
Point p[n];
for (int i = 0; i < n; ++i) {
cin >> p[i].x >> p[i].y;
}
sort(p, p+n, cmp_x);
cout << closest_pair(p, n) << endl;
return 0;
}