用C语言写一个求平面上两个的最短距离并体现分治思想
时间: 2023-05-28 15:05:04 浏览: 42
#include <stdio.h>
#include <math.h>
typedef struct {
double x;
double y;
} Point;
double distance(Point a, Point b) {
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double min(double a, double b) {
return a < b ? a : b;
}
double closest(Point points[], int n) {
if (n <= 1) {
return INFINITY;
} else if (n == 2) {
return distance(points[0], points[1]);
}
int mid = n / 2;
Point midPoint = points[mid];
double d = min(closest(points, mid), closest(points + mid, n - mid));
Point strip[n];
int j = 0;
for (int i = 0; i < n; i++) {
if (fabs(points[i].x - midPoint.x) < d) {
strip[j++] = points[i];
}
}
for (int i = 0; i < j - 1; i++) {
for (int k = i + 1; k < j && strip[k].y - strip[i].y < d; k++) {
double dist = distance(strip[i], strip[k]);
if (dist < d) {
d = dist;
}
}
}
return d;
}
int main() {
Point points[] = {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}};
int n = sizeof(points) / sizeof(points[0]);
printf("The minimum distance is %lf", closest(points, n));
return 0;
}