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函數來計算凸包，并輸出凸包的點。