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

凸包问题是计算几何学中的经典问题，可以使用分治法进行解决。下面是使用C语言实现的分治法解决凸包问题的示例代码：

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

// 定义二维坐标点结构体
typedef struct {
    int x;
    int y;
} Point;

// 计算两点之间的距离
double dist(Point a, Point b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

// 计算三个点构成的三角形面积
double triangleArea(Point a, Point b, Point c) {
    return abs(a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x) / 2.0;
}

// 求解凸包
void convexHull(Point points[], int n, Point hull[], int *hullSize) {
    // 基本情况
    if (n <= 1) {
        *hullSize = n;
        hull[0] = points[0];
        return;
    }
    
    // 分治
    int mid = n / 2;
    Point leftHull[mid + 1];
    Point rightHull[n - mid + 1];
    int leftHullSize, rightHullSize;
    convexHull(points, mid, leftHull, &leftHullSize);
    convexHull(points + mid, n - mid, rightHull, &rightHullSize);
    
    // 合并
    int leftIndex = 0, rightIndex = 0;
    int bottomLeftIndex = 0, bottomRightIndex = 0, topLeftIndex = 0, topRightIndex = 0;
    for (int i = 0; i < leftHullSize + rightHullSize; i++) {
        if (leftIndex == leftHullSize) {
            hull[i] = rightHull[rightIndex++];
        } else if (rightIndex == rightHullSize) {
            hull[i] = leftHull[leftIndex++];
        } else if (leftHull[leftIndex].x < rightHull[rightIndex].x) {
            hull[i] = leftHull[leftIndex++];
        } else {
            hull[i] = rightHull[rightIndex++];
        }
        
        // 更新最下面的点的索引
        if (hull[i].y < hull[bottomLeftIndex].y) {
            bottomLeftIndex = i;
        }
        if (hull[i].y < hull[bottomRightIndex].y) {
            bottomRightIndex = i;
        }
    }
    
    // 求解上凸壳
    for (int i = bottomLeftIndex; i >= 0; i--) {
        while (topLeftIndex >= 2 && triangleArea(hull[topLeftIndex - 2], hull[topLeftIndex - 1], hull[i]) <= 0) {
            topLeftIndex--;
        }
        hull[topLeftIndex++] = hull[i];
    }
    for (int i = bottomRightIndex; i < leftHullSize + rightHullSize; i++) {
        while (topRightIndex >= 2 && triangleArea(hull[topRightIndex - 2], hull[topRightIndex - 1], hull[i]) <= 0) {
            topRightIndex--;
        }
        hull[topRightIndex++] = hull[i];
    }
    
    // 更新凸壳大小
    *hullSize = topLeftIndex + topRightIndex - 2;
}

int main() {
    // 定义点集
    Point points[] = {{0, 0}, {1, 1}, {2, 2}, {3, -1}, {4, 4}, {5, 3}, {6, 2}, {7, 1}, {8, 0}, {9, -1}};
    int n = sizeof(points) / sizeof(Point);
    
    // 求解凸包
    Point hull[n];
    int hullSize;
    convexHull(points, n, hull, &hullSize);
    
    // 输出凸包
    printf("Convex Hull:\n");
    for (int i = 0; i < hullSize; i++) {
        printf("(%d, %d) ", hull[i].x, hull[i].y);
    }
    printf("\n");
    
    return 0;
}

该示例代码使用分治法求解凸包，首先将点集分成左右两部分，然后递归地求解左右两部分的凸包。接着合并左右两部分的凸包，找到最下面的点，并分别求解上凸壳。最后输出凸包即可。

需要注意的是，在合并左右两部分的凸包时，使用了类似归并排序的方法，将左右两部分按照x坐标大小进行排序。同时，需要使用三角形面积的方法判断上凸壳。