C++算法库中的凸包算法实现

C++算法库中常用的凸包算法实现是Graham Scan算法。以下是一个简单的实现示例：

#include <iostream>
#include <vector>
#include <algorithm>

struct Point {
    int x, y;
};

// 用于比较两个点的极角
bool compare(Point a, Point b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

// 计算两点之间的叉积
int crossProduct(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// Graham Scan算法
std::vector<Point> convexHull(std::vector<Point>& points) {
    int n = points.size();
    if (n < 3) {
        return points;
    }

    std::sort(points.begin(), points.end(), compare);

    std::vector<Point> hull;
    // 下凸壳
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && crossProduct(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    // 上凸壳
    int t = hull.size() + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() >= t && crossProduct(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }

    hull.pop_back(); // 移除重复的起始点
    return hull;
}

int main() {
    std::vector<Point> points = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};
    std::vector<Point> hull = convexHull(points);

    std::cout << "Convex Hull Points:\n";
    for (Point p : hull) {
        std::cout << "(" << p.x << ", " << p.y << ")\n";
    }

    return 0;
}

在这个示例中，我们首先定义了一个Point结构体用于表示二维点的坐标。然后实现了比较两个点的极角的比较函数compare和计算两点之间的叉积的函数crossProduct。最后实现了Graham Scan算法函数convexHull来计算凸包。

在main函数中，我们定义了一些二维点，并调用convexHull函数来计算凸包，并输出凸包的点。