凸包问题分治算法C++

凸包问题是指在一个点集中找到包围所有点的最小凸多边形的过程。在计算机图形学和算法设计中，分治法是一种常用的方法来解决这个问题，尤其是对最简单的凸包算法—— Gift Wrapping 或者扫描线算法。

Gift Wrapping 算法又称为“蛇形”算法，其基本思想是遍历点集，从第一个点开始，沿着顺时针方向依次检查每个点是否在其右侧的凸包上。如果发现不在，就调整当前凸包边界直到包含该点。最后，这个凸包包含了所有的点。

在 C++ 中，你可以按照以下步骤编写 Gift Wrapping 算法：

1. 定义一个结构体或类来存储二维坐标，并实现比较函数用于判断点的位置。

struct Point {
    int x, y;
    bool operator<(const Point& other) const { return y < other.y || (y == other.y && x < other.x); }
};

2. 使用优先队列存储点的顺序，初始化时将第一个点入队。

std::priority_queue<Point> points;
points.push({x1, y1}); // 其中 (x1, y1) 是第一个点

3. 分治处理过程：
- 取出队首点作为当前边界左端点 `current`。
- 当队列非空时，不断取出下一个点 `next`，如果 `next` 在 `current` 和其余点围成的凸包右边，则移动边界到 `next`。
4. 最终，凸包由 `current` 和所有处理过的点构成。