请用c语言代码实现下面问题:设是平面上散列的个点的集合。请编写程序找出集合中距离最近的点对的距离。 输入格式: 输入第一行给出一个正整数,表示平面上点的数量。随后行,每行给出一个实数对,每个实数对表示一个点的坐标值,其中第1数表示横坐标,第2数表示纵坐标。 输出格式: 最近点对中两个点之间的距离。 输入样例: 5 -1.00 2.00 0.00 2.00 0.50 0.60 1.00 1.00 2.00 0.00 输出样例: 0.6403 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
时间: 2024-03-18 12:39:57 浏览: 19
以下是基于分治算法的 C 语言代码实现,时间复杂度为 O(nlogn):
```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct point {
double x;
double y;
} Point;
int cmp_x(const void *a, const void *b) {
Point *pa = (Point *)a;
Point *pb = (Point *)b;
return pa->x > pb->x ? 1 : -1;
}
int cmp_y(const void *a, const void *b) {
Point *pa = (Point *)a;
Point *pb = (Point *)b;
return pa->y > pb->y ? 1 : -1;
}
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 pts[], int n) {
double min_dist = 1e20;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double d = dist(pts[i], pts[j]);
if (d < min_dist)
min_dist = d;
}
}
return min_dist;
}
double strip_closest(Point strip[], int n, double d) {
double min_dist = d;
qsort(strip, n, sizeof(Point), cmp_y);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n && (strip[j].y - strip[i].y) < min_dist; j++) {
double d = dist(strip[i], strip[j]);
if (d < min_dist)
min_dist = d;
}
}
return min_dist;
}
double closest_pair(Point pts[], int n) {
if (n <= 3)
return brute_force(pts, n);
int mid = n / 2;
Point midpt = pts[mid];
double dl = closest_pair(pts, mid);
double dr = closest_pair(pts + mid, n - mid);
double d = fmin(dl, dr);
Point strip[n];
int j = 0;
for (int i = 0; i < n; i++) {
if (fabs(pts[i].x - midpt.x) < d)
strip[j++] = pts[i];
}
return fmin(d, strip_closest(strip, j, d));
}
int main() {
int n;
scanf("%d", &n);
Point pts[n];
for (int i = 0; i < n; i++) {
scanf("%lf %lf", &pts[i].x, &pts[i].y);
}
qsort(pts, n, sizeof(Point), cmp_x);
printf("%.4lf\n", closest_pair(pts, n));
return 0;
}
```
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)