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

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

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

typedef struct {
    int x;
    int y;
} Point;

int orientation(Point p, Point q, Point r) {
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) {
        return 0;
    } else {
        return (val > 0) ? 1 : 2;
    }
}

void convexHullUtil(Point points[], int n, Point hull[], int* k) {
    if (n < 3) {
        return;
    }
    Point* left_half = (Point*) malloc(n * sizeof(Point));
    Point* right_half = (Point*) malloc(n * sizeof(Point));
    int left_half_size = 0, right_half_size = 0;
    int middle = n / 2;
    for (int i = 0; i < middle; i++) {
        left_half[left_half_size++] = points[i];
    }
    for (int i = middle; i < n; i++) {
        right_half[right_half_size++] = points[i];
    }
    Point* left_hull = (Point*) malloc(left_half_size * sizeof(Point));
    Point* right_hull = (Point*) malloc(right_half_size * sizeof(Point));
    int left_hull_size = 0, right_hull_size = 0;
    convexHullUtil(left_half, left_half_size, left_hull, &left_hull_size);
    convexHullUtil(right_half, right_half_size, right_hull, &right_hull_size);
    int l = 0, r = 0;
    while (l < left_hull_size && r < right_hull_size) {
        hull[(*k)++] = left_hull[l++];
        hull[(*k)++] = right_hull[r++];
    }
    while (l < left_hull_size) {
        hull[(*k)++] = left_hull[l++];
    }
    while (r < right_hull_size) {
        hull[(*k)++] = right_hull[r++];
    }
    free(left_half);
    free(right_half);
    free(left_hull);
    free(right_hull);
}

void convexHull(Point points[], int n) {
    Point* hull = (Point*) malloc(n * sizeof(Point));
    int k = 0;
    convexHullUtil(points, n, hull, &k);
    for (int i = 0; i < k; i++) {
        printf("(%d, %d)\n", hull[i].x, hull[i].y);
    }
    free(hull);
}

int main() {
    Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

该代码中用到了递归的思想，将点集分成左右两半，分别求出左半部分和右半部分的凸包，然后将两个凸包合并起来。其中，求解左右半部分的凸包也是通过递归实现的。

时间复杂度为 O(n log n)。