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;
}