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

凸包问题是计算几何中的一个经典问题。分治法是解决凸包问题的一种常用方法。

具体步骤如下：

1. 将所有点按照 x 坐标排序，如果 x 坐标相同，则按照 y 坐标排序。
2. 把所有点分成两个部分，分别求出左侧和右侧的凸包。
3. 合并左侧凸包和右侧凸包，得到最终的凸包。

下面是用 C 语言实现的示例代码：

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

struct Point {
    int x, y;
};

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

int cross(const struct Point* a, const struct Point* b, const struct Point* c) {
    return (b->x - a->x) * (c->y - a->y) - (b->y - a->y) * (c->x - a->x);
}

void convex_hull(struct Point* points, int n, struct Point* hull, int* m) {
    qsort(points, n, sizeof(struct Point), compare);
    *m = 0;
    for (int i = 0; i < n; i++) {
        while (*m >= 2 && cross(&hull[*m-2], &hull