c++分治实现平面凸包问题

要使用分治算法来解决平面凸包问题，可以按照以下步骤进行：

1. 将给定的点集按照 x 坐标进行排序，如果 x 坐标相同，则按照 y 坐标排序。
2. 将点集分成两个子集，每个子集包含大约一半的点。可以选择一个 x 坐标值作为分割线，将点集分成左右两个子集，或者选择中间的点作为分割线。
3. 对左右两个子集分别进行递归处理，得到左右两个子集的凸包。
4. 合并左右两个子集的凸包，得到整个点集的凸包。

在每一次递归中，可以使用 Graham 扫描算法或者快速凸包算法来求解子集的凸包。

以下是一个用 C++ 实现的示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
};

// 按照 x 坐标进行排序，如果 x 坐标相同，则按照 y 坐标排序
bool compareX(Point p1, Point p2) {
    if (p1.x == p2.x)
        return p1.y < p2.y;
    return p1.x < p2.x;
}

// 按照极角排序，极角相同则按照距离原点的距离排序
bool compareAngle(Point p1, Point p2) {
    int cross = (p1.x - p[0].x) * (p2.y - p[0].y) - (p2.x - p[0].x) * (p1.y - p[0].y);
    if (cross == 0)
        return (p1.x - p[0].x) * (p1.x - p[0].x) + (p1.y - p[0].y) * (p1.y - p[0].y) < (p2.x - p[0].x) * (p2.x - p[0].x) + (p2.y - p[0].y) * (p2.y - p[0].y);
    return cross > 0;
}

// 计算凸包
vector<Point> convexHull(vector<Point>& points, int left, int right) {
    if (left == right) {
        vector<Point> hull;
        hull.push_back(points[left]);
        return hull;
    }
    int mid = (left + right) / 2;
    vector<Point> hullLeft = convexHull(points, left, mid);
    vector<Point> hullRight = convexHull(points, mid + 1, right);
    int sizeLeft = hullLeft.size();
    int sizeRight = hullRight.size();

    // 合并左右凸包
    int leftmost = 0, rightmost = 0;
    for (int i = 1; i < sizeLeft; i++) {
        if (hullLeft[i].x < hullLeft[leftmost].x)
            leftmost = i;
    }
    for (int i = 1; i < sizeRight; i++) {
        if (hullRight[i].x > hullRight[rightmost].x)
            rightmost = i;
    }
    int lowerLeft = leftmost, lowerRight = rightmost;
    while (true) {
        int newLowerLeft = (lowerLeft + sizeLeft - 1) % sizeLeft;
        int cross = (hullLeft[lowerLeft].x - hullLeft[newLowerLeft].x) * (hullRight[lowerRight].y - hullLeft[newLowerLeft].y) - (hullRight[lowerRight].x - hullLeft[newLowerLeft].x) * (hullLeft[lowerLeft].y - hullLeft[newLowerLeft].y);
        if (cross < 0)
            break;
        lowerLeft = newLowerLeft;
    }
    while (true) {
        int newLowerRight = (lowerRight + 1) % sizeRight;
        int cross = (hullRight[lowerRight].x - hullLeft[lowerLeft].x) * (hullRight[newLowerRight].y - hullLeft[lowerLeft].y) - (hullRight[newLowerRight].x - hullLeft[lowerLeft].x) * (hullRight[lowerRight].y - hullLeft[lowerLeft].y);
        if (cross < 0)
            break;
        lowerRight = newLowerRight;
    }
    vector<Point> hull;
    int current = lowerLeft;
    while (current != lowerRight) {
        hull.push_back(hullLeft[current]);
        current = (current + 1) % sizeLeft;
    }
    hull.push_back(hullLeft[current]);
    current = lowerRight;
    while (current != lowerLeft) {
        hull.push_back(hullRight[current]);
        current = (current + 1) % sizeRight;
    }
    hull.push_back(hullRight[current]);
    return hull;
}

vector<Point> convexHull(vector<Point>& points) {
    int n = points.size();
    if (n < 3) {
        return points;
    }
    sort(points.begin(), points.end(), compareX);
    return convexHull(points, 0, n - 1);
}

int main() {
    vector<Point> points = { {0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3} };
    vector<Point> hull = convexHull(points);
    for (int i = 0; i < hull.size(); i++) {
        cout << "(" << hull[i].x << ", " << hull[i].y << ")" << endl;
    }
    return 0;
}

这段代码使用分治算法来解决平面凸包问题，其中 `convexHull` 函数实现了分治过程，`compareX` 和 `compareAngle` 函数用于排序，`main` 函数中的示例展示了如何使用该函数来求解平面凸包问题。你可以将自己的点集替换到 `points` 数组中进行测试。