分治算法求最邻近点对C语言

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define INF 1e9 //定义无穷大

typedef struct Point {
double x, y;
} point;

int cmpx(const void *a, const void *b) { //按x坐标排序的比较函数
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;
}

int cmpy(const void *a, const void *b) { //按y坐标排序的比较函数
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(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

double min(double x, double y) { //返回两个数中较小的数
return x < y ? x : y;
}

double closestPair(point *p, int n) {
double d, d1, d2, d3, dmin; //d为当前最短距离，d1,d2,d3为分治后的三部分最短距离
int i, j, k, m;
point *p1, *p2;
if (n <= 1) return INF; //若点数小于等于1，则返回无穷大
if (n == 2) return dist(p[0], p[1]); //若点数等于2，则返回这两个点的距离
qsort(p, n, sizeof(point), cmpx); //按x坐标排序
m = n / 2; //取中点
d1 = closestPair(p, m); //递归求左半部分的最短距离
d2 = closestPair(p + m, n - m); //递归求右半部分的最短距离
d = min(d1, d2); //取左右两部分中的最短距离
point *strip = (point *)malloc(n * sizeof(point)); //分配存储跨越中线的点的数组
j = 0;
for (i = 0; i < n; i++) { //将横坐标距离中线小于d的点复制到strip数组中
if (fabs(p[i].x - p[m].x) < d) {
strip[j] = p[i];
j++;
}
}
qsort(strip, j, sizeof(point), cmpy); //按y坐标排序
dmin = d;
for (i = 0; i < j; i++) { //在strip数组中找距离不超过d的最近点对
for (k = i + 1; k < j && strip[k].y - strip[i].y < dmin; k++) {
d3 = dist(strip[i], strip[k]);
if (d3 < dmin) {
dmin = d3;
p1 = &strip[i];
p2 = &strip[k];
}
}
}
free(strip); //释放strip数组
if (dmin < d) return dmin; //返回strip数组中的最近点对距离
else return d; //返回左右两部分的最近点对距离
}

int main() {
int n, i;
printf("Please input the number of points:\n");
scanf("%d", &n);
point *p = (point *)malloc(n * sizeof(point)); //分配存储点的数组
printf("Please input the coordinates of the points:\n");
for (i = 0; i < n; i++) {
scanf("%lf%lf", &p[i].x, &p[i].y);
}
printf("The closest pair distance is %lf.\n", closestPair(p, n)); //输出最近点对距离
free(p); //释放p数组
return 0;
}