用分治算法解决最小凸包问题的c语言代码

以下是使用分治算法解决最小凸包问题的 C 语言代码：

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

#define MAX_POINTS 100000

typedef struct point {
    double x, y;
} Point;

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

int compare_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) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx * dx + dy * dy);
}

double min(double a, double b) {
    return a < b ? a : b;
}

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

double strip_min_dist(Point strip[], int n, double d) {
    double min_dist = d;
    qsort(strip, n, sizeof(Point), compare_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_util(Point points[], int n) {
    if (n <= 3) {
        return brute_force(points, n);
    }
    int mid = n / 2;
    Point mid_point = points[mid];
    double dl = closest_util(points, mid);
    double dr = closest_util(points + mid, n - mid);
    double d = min(dl, dr);
    Point strip[n];
    int j = 0;
    for (int i = 0; i < n; i++) {
        if (abs(points[i].x - mid_point.x) < d) {
            strip[j] = points[i];
            j++;
        }
    }
    return min(d, strip_min_dist(strip, j, d));
}

double closest_pair(Point points[], int n) {
    qsort(points, n, sizeof(Point), compare_x);
    return closest_util(points, n);
}

int main() {
    int n;
    Point points[MAX_POINTS];
    printf("Enter the number of points: ");
    scanf("%d", &n);
    printf("Enter the points (x y):\n");
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &points[i].x, &points[i].y);
    }
    double closest = closest_pair(points, n);
    printf("The closest pair of points is %lf apart.\n", closest);
    return 0;
}

该代码使用了分治算法解决最小凸包问题，其中 `closest_util` 函数实现了分治算法的核心部分，使用了 `brute_force` 函数处理小规模问题，使用了 `strip_min_dist` 函数处理跨越中心线的最小距离。该代码的时间复杂度为 O(nlogn)。