分治算法二维点对最小距离的c++代码

以下是分治算法二维点对最小距离的 C 代码：

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

#define MAXN 100000

typedef struct {
double x, y;
} Point;

int cmp_x(const void* a, const void* b) {
Point* p1 = (Point*)a;
Point* p2 = (Point*)b;
if (p1->x < p2->x) return -1;
if (p1->x > p2->x) return 1;
if (p1->y < p2->y) return -1;
if (p1->y > p2->y) return 1;
return ;
}

int cmp_y(const void* a, const void* b) {
Point* p1 = (Point*)a;
Point* p2 = (Point*)b;
if (p1->y < p2->y) return -1;
if (p1->y > p2->y) return 1;
if (p1->x < p2->x) return -1;
if (p1->x > p2->x) return 1;
return ;
}

double dist(Point* p1, Point* p2) {
double dx = p1->x - p2->x;
double dy = p1->y - p2->y;
return sqrt(dx*dx + dy*dy);
}

double brute_force(Point* p, int n) {
double min_dist = 1e20;
for (int i = ; i < n; 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 closest_pair(Point* px, Point* py, int n) {
if (n <= 3) return brute_force(px, n);
int mid = n / 2;
Point mid_point = px[mid];
Point pyl[mid+1], pyr[n-mid-1];
int li = , ri = ;
for (int i = ; i < n; i++) {
if (py[i].x < mid_point.x || (py[i].x == mid_point.x && py[i].y < mid_point.y)) {
pyl[li++] = py[i];
} else {
pyr[ri++] = py[i];
}
}
double dl = closest_pair(px, pyl, mid);
double dr = closest_pair(px+mid, pyr, n-mid);
double d = fmin(dl, dr);
Point strip[n];
int j = ;
for (int i = ; i < n; i++) {
if (fabs(py[i].x - mid_point.x) < d) {
strip[j++] = py[i];
}
}
for (int i = ; i < j; i++) {
for (int k = i+1; k < j && strip[k].y - strip[i].y < d; k++) {
double dij = dist(&strip[i], &strip[k]);
if (dij < d) d = dij;
}
}
return d;
}

int main() {
int n;
Point p[MAXN], px[MAXN], py[MAXN];
scanf("%d", &n);
for (int i = ; i < n; i++) {
scanf("%lf%lf", &p[i].x, &p[i].y);
}
qsort(p, n, sizeof(Point), cmp_x);
for (int i = ; i < n; i++) {
px[i] = py[i] = p[i];
}
qsort(py, n, sizeof(Point), cmp_y);
printf("%.2lf\n", closest_pair(px, py, n));
return ;
}