使用C语言写出分制法求解最近对问题程序代码

以下是使用C语言编写的分治法求解最近点对问题的程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Point {
    double x;
    double y;
};

int cmp_x(const void* a, const void* b) {
    struct Point* p1 = (struct Point*)a;
    struct Point* p2 = (struct Point*)b;
    return (p1->x > p2->x);
}

int cmp_y(const void* a, const void* b) {
    struct Point* p1 = (struct Point*)a;
    struct Point* p2 = (struct Point*)b;
    return (p1->y > p2->y);
}

double distance(struct Point p1, struct Point p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx * dx + dy * dy);
}

double min(double x, double y) {
    return (x < y) ? x : y;
}

double brute_force(struct Point p[], int n) {
    double min_dist = distance(p[0], p[1]);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            double dist = distance(p[i], p[j]);
            if (dist < min_dist) {
                min_dist = dist;
            }
        }
    }
    return min_dist;
}

double strip_closest(struct Point strip[], int size, double d) {
    double min_dist = d;
    qsort(strip, size, sizeof(struct Point), cmp_y);
    for (int i = 0; i < size; ++i) {
        for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min_dist; ++j) {
            double dist = distance(strip[i], strip[j]);
            if (dist < min_dist) {
                min_dist = dist;
            }
        }
    }
    return min_dist;
}

double closest_util(struct Point p[], int n) {
    if (n <= 3) {
        return brute_force(p, n);
    }
    int mid = n / 2;
    struct Point mid_point = p[mid];
    double dl = closest_util(p, mid);
    double dr = closest_util(p + mid, n - mid);
    double d = min(dl, dr);
    struct Point strip[n];
    int j = 0;
    for (int i = 0; i < n; ++i) {
        if (abs(p[i].x - mid_point.x) < d) {
            strip[j] = p[i], j++;
        }
    }
    return min(d, strip_closest(strip, j, d));
}

double closest(struct Point p[], int n) {
    qsort(p, n, sizeof(struct Point), cmp_x);
    return closest_util(p, n);
}

int main() {
    struct Point p[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
    int n = sizeof(p) / sizeof(p[0]);
    printf("The smallest distance is %lf", closest(p, n));
    return 0;
}

该程序使用分治法求解最近点对问题，首先将所有点按照x坐标从小到大排序，然后递归地将点集分成两部分，分别求解左右两部分的最近点对距离，然后取两者的最小值。接下来，需要考虑横跨两部分的最近点对距离。将两个部分的中间点的x坐标的中点作为分界线，将点集中的点按照y坐标从小到大排序，计算分界线两侧距离小于最近点对距离d的点集strip，并对strip中的点按照y坐标从小到大排序，然后计算strip中所有点两两之间的距离，取最小值作为横跨两部分的最近点对距离。