C++算法庫(kù)中的凸包算法實(shí)現(xiàn)

C++算法庫(kù)中常用的凸包算法實(shí)現(xiàn)是Graham Scan算法。以下是一個(gè)簡(jiǎn)單的實(shí)現(xiàn)示例：

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

struct Point {
    int x, y;
};

// 用于比較兩個(gè)點(diǎn)的極角
bool compare(Point a, Point b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

// 計(jì)算兩點(diǎn)之間的叉積
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(); // 移除重復(fù)的起始點(diǎn)
    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;
}

在這個(gè)示例中，我們首先定義了一個(gè)Point結(jié)構(gòu)體用于表示二維點(diǎn)的坐標(biāo)。然后實(shí)現(xiàn)了比較兩個(gè)點(diǎn)的極角的比較函數(shù)compare和計(jì)算兩點(diǎn)之間的叉積的函數(shù)crossProduct。最后實(shí)現(xiàn)了Graham Scan算法函數(shù)convexHull來計(jì)算凸包。

在main函數(shù)中，我們定義了一些二維點(diǎn)，并調(diào)用convexHull函數(shù)來計(jì)算凸包，并輸出凸包的點(diǎn)。