用分治算法求最邻近点对C语言
时间: 2023-05-20 18:02:33 浏览: 80
可以使用分治算法来求解最邻近点对问题。具体实现步骤如下:
1. 将所有点按照横坐标排序,如果横坐标相同则按照纵坐标排序。
2. 将点集分成左右两个部分,分别递归求解左右两个部分的最邻近点对。
3. 计算左右两个部分中距离最小的点对,记为d。
4. 将所有横坐标与d的横坐标之差小于d的点按照纵坐标排序。
5. 在排序后的点集中,对于每个点,只需要考虑与其纵坐标之差小于d的点的距离即可。
6. 对于每个点,只需要考虑与其纵坐标之差小于d的点的距离即可。
7. 在这些点中,找到距离最小的点对,记为d'。
8. 返回d和d'中距离最小的点对。
以下是C语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_N 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 0;
}
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 0;
}
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 closest_pair(Point *p, int n) {
if (n <= 1) return INFINITY;
int m = n / 2;
double x = p[m].x;
double d = fmin(closest_pair(p, m), closest_pair(p + m, n - m));
qsort(p, n, sizeof(Point), cmp_y);
Point *t = (Point *)malloc(n * sizeof(Point));
int k = 0;
for (int i = 0; i < n; i++) {
if (fabs(p[i].x - x) >= d) continue;
for (int j = k - 1; j >= 0; j--) {
double dy = p[i].y - t[j].y;
if (dy >= d) break;
double td = dist(p[i], t[j]);
if (td < d) d = td;
}
t[k++] = p[i];
}
free(t);
return d;
}
int main() {
int n;
Point p[MAX_N];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lf%lf", &p[i].x, &p[i].y);
}
qsort(p, n, sizeof(Point), cmp_x);
printf("%.2f\n", closest_pair(p, n));
return 0;
}
```
该算法的时间复杂度为O(nlogn)。