分治法求解凸包 c++完整代码

分治法求解凸包通常涉及使用扫描线算法（如Monotone Chain Algorithm），这个算法利用了凸多边形的一个特性：在垂直扫描线上，顶点按照从左到右的顺序排列，并且不会交叉。

以下是一个简单的 C++ 代码示例，实现了基于分治法的凸包计算：

#include <vector>
#include <stack>

struct Point {
    int x;
    int y;
};

Point get_leftmost_top(const std::vector<Point>& points) {
    return points[0];
}

Point get_rightmost_top(const std::vector<Point>& points) {
    return points.rbegin()->x > points.front().x ? *points.rbegin() : points.front();
}

std::vector<Point> convex_hull_sorted(std::vector<Point>& points) {
    if (points.size() <= 2) {
        return points;
    }

    std::sort(points.begin(), points.end(), [](const Point& a, const Point& b) { return a.y == b.y ? a.x < b.x : a.y < b.y; });

    Point leftmost_top = get_leftmost_top(points);
    Point rightmost_top = get_rightmost_top(points);

    std::stack<Point> stack;
    stack.push(leftmost_top);
    stack.push(rightmost_top);

    for (size_t i = 1; i < points.size(); ++i) {
        while (!stack.empty() && points[i].y >= stack.top().y) {
            Point top = stack.top();
            stack.pop();
            if (points[i].x <= top.x) {
                stack.push(top);
            }
        }
        stack.push(points[i]);
    }

    std::vector<Point> result(stack.size());
    std::copy(stack.begin(), stack.end(), result.begin());

    return result;
}