分治法解决凸包问题的c语言代码

分治法解决凸包问题的C语言代码如下：

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

typedef struct Point {
    double x;
    double 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 distance(Point p1, Point p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx * dx + dy * dy);
}

double cross_product(Point p1, Point p2, Point p3) {
    double x1 = p2.x - p1.x;
    double y1 = p2.y - p1.y;
    double x2 = p3.x - p2.x;
    double y2 = p3.y - p2.y;
    return x1 * y2 - x2 * y1;
}

void merge(Point *points, int left, int mid, int right, Point *buffer) {
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (points[i].y < points[j].y) {
            buffer[k++] = points[i++];
        } else {
            buffer[k++] = points[j++];
        }
    }
    while (i <= mid) {
        buffer[k++] = points[i++];
    }
    while (j <= right) {
        buffer[k++] = points[j++];
    }
    for (i = left, k = 0; i <= right; i++, k++) {
        points[i] = buffer[k];
    }
}

double closest_pair(Point *points, int left, int right, Point *buffer) {
    double d1, d2, d, l, r;
    int i, j, k, mid;
    Point *p, *q;
    if (left == right) {
        return INFINITY;
    } else if (left + 1 == right) {
        return distance(points[left], points[right]);
    }
    mid = (left + right) / 2;
    d1 = closest_pair(points, left, mid, buffer);
    d2 = closest_pair(points, mid + 1, right, buffer);
    d = fmin(d1, d2);
    merge(points, left, mid, right, buffer);
    for (i = left; i <= right; i++) {
        if (fabs(points[i].x - points[mid].x) >= d) {
            continue;
        }
        for (j = i + 1; j <= right; j++) {
            if (fabs(points[j].x - points[mid].x) >= d) {
                break;
            }
            if (distance(points[i], points[j]) < d) {
                d = distance(points[i], points[j]);
            }
        }
    }
    return d;
}

double convex_hull(Point *points, int n, Point *hull) {
    int i, k, t;
    qsort(points, n, sizeof(Point), compare_x);
    for (i = 0; i < n; i++) {
        while (k >= 2 && cross_product(hull[k - 2], hull[k - 1], points[i]) <= 0) {
            k--;
        }
        hull[k++] = points[i];
    }
    for (i = n - 2, t = k + 1; i >= 0; i--) {
        while (k >= t && cross_product(hull[k - 2], hull[k - 1], points[i]) <= 0) {
            k--;
        }
        hull[k++] = points[i];
    }
    return k;
}

int main() {
    int n, i;
    Point *points, *hull, *buffer;
    double d;
    scanf("%d", &n);
    points = (Point *)malloc(n * sizeof(Point));
    hull = (Point *)malloc(n * sizeof(Point));
    buffer = (Point *)malloc(n * sizeof(Point));
    for (i = 0; i < n; i++) {
        scanf("%lf %lf", &points[i].x, &points[i].y);
    }
    d = closest_pair(points, 0, n - 1, buffer);
    printf("%.2f\n", d);
    n = convex_hull(points, n, hull);
    for (i = 0; i < n; i++) {
        printf("%.0f %.0f\n", hull[i].x, hull[i].y);
    }
    free(points);
    free(hull);
    free(buffer);
    return 0;
}

代码中使用了两个辅助函数：compare_x 和 compare_y，分别用于按照 x 坐标和 y 坐标对点进行排序。distance 函数用于计算两个点之间的距离。cross_product 函数用于计算三个点构成的向量的叉积。

closest_pair 函数使用分治法解决最近点对问题。首先将点集按照 x 坐标排序，然后将点集分为两个部分，对左右两个部分分别递归调用 closest_pair 函数，得到左右两部分的最近点对距离 d1 和 d2。然后将左右两部分的点集按照 y 坐标排序，将它们合并成一个有序点集，并且对于每个点，只需要考虑与它 y 坐标相差不超过 d 的点集中的点即可，这一步可以通过一个双重循环实现。最后返回最小距离 d。

convex_hull 函数用于求解凸包。首先按照 x 坐标排序，然后从左到右依次加入点，如果加入点导致凸包不满足条件，则需要将凸包中右侧的点删除，直到凸包恢复为合法的凸包。然后从右到左依次加入点，也是同样的操作。最后返回凸包的点数。