C语言利用分治法解决凸包问题

凸包问题是计算几何学中的经典问题，可以通过分治法来解决。下面给出 C 语言实现的分治法求解凸包问题的代码：

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

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

double cross(point a, point b, point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

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

void mergeSort(point* points, int left, int right, point* temp) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(points, left, mid, temp);
        mergeSort(points, mid + 1, right, temp);
        merge(points, left, mid, right, temp);
    }
}

void divide(point* points, int left, int right, point* hull, int* size) {
    if (right - left + 1 <= 3) {
        for (int i = left; i <= right; i++) {
            hull[(*size)++] = points[i];
        }
        return;
    }
    int mid = (left + right) / 2;
    point* leftHull = (point*) malloc(sizeof(point) * (right - left + 1));
    int leftSize = 0;
    divide(points, left, mid, leftHull, &leftSize);
    point* rightHull = (point*) malloc(sizeof(point) * (right - left + 1));
    int rightSize = 0;
    divide(points, mid + 1, right, rightHull, &rightSize);
    point* temp = (point*) malloc(sizeof(point) * (right - left + 1));
    merge(leftHull, 0, leftSize - 1, rightHull, 0, rightSize - 1, temp);
    int tempSize = 0;
    for (int i = 0; i < leftSize; i++) {
        while (tempSize >= 2 && cross(hull[tempSize - 2], hull[tempSize - 1], leftHull[i]) <= 0) {
            tempSize--;
        }
        hull[tempSize++] = leftHull[i];
    }
    for (int i = rightSize - 1; i >= 0; i--) {
        while (tempSize >= 2 && cross(hull[tempSize - 2], hull[tempSize - 1], rightHull[i]) <= 0) {
            tempSize--;
        }
        hull[tempSize++] = rightHull[i];
    }
    *size = tempSize;
    free(leftHull);
    free(rightHull);
    free(temp);
}

void convexHull(point* points, int n, point* hull, int* size) {
    point* temp = (point*) malloc(sizeof(point) * n);
    mergeSort(points, 0, n - 1, temp);
    divide(points, 0, n - 1, hull, size);
    free(temp);
}

int main() {
    int n = 5;
    point points[] = {{0, 0}, {1, 1}, {2, 2}, {3, 1}, {4, 0}};
    point* hull = (point*) malloc(sizeof(point) * n);
    int size = 0;
    convexHull(points, n, hull, &size);
    for (int i = 0; i < size; i++) {
        printf("(%lf, %lf)\n", hull[i].x, hull[i].y);
    }
    free(hull);
    return 0;
}

这段代码首先定义了一个结构体 `point` 表示二维平面上的点，然后实现了求叉积的函数 `cross`。接着实现了归并排序的函数 `merge` 和 `mergeSort`，用于按照横坐标进行排序。最后实现了分治法求解凸包问题的函数 `divide` 和 `convexHull`，其中 `divide` 是核心函数，用于将点集分成左右两个集合，分别递归求解，并将两个凸包合并成一个。最后在 `main` 函数中给出了一个测试用例。