凸包算法c++实现代码

以下是C++的凸包算法实现代码，使用的是Graham Scan算法：

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
};

// 求出两点之间的距离平方
int dist_square(Point p1, Point p2) {
    int x = p1.x - p2.x;
    int y = p1.y - p2.y;
    return x * x + y * y;
}

// 求出叉积
int cross_product(Point a, Point b, Point c) {
    int x1 = b.x - a.x;
    int y1 = b.y - a.y;
    int x2 = c.x - b.x;
    int y2 = c.y - b.y;
    return x1 * y2 - x2 * y1;
}

// 比较两点的极角大小
bool cmp(Point a, Point b) {
    int cp = cross_product(p0, a, b);
    if (cp > 0) return true;
    if (cp == 0 && dist_square(p0, a) < dist_square(p0, b)) return true;
    return false;
}

// Graham Scan算法
void convex_hull(Point points[], int n) {
    // 找出y坐标最小的点
    int ymin = points[0].y, min_idx = 0;
    for (int i = 1; i < n; i++) {
        int y = points[i].y;
        if ((y < ymin) || (ymin == y && points[i].x < points[min_idx].x)) {
            ymin = y;
            min_idx = i;
        }
    }

    // 将y坐标最小的点放到首位
    swap(points[0], points[min_idx]);
    p0 = points[0];

    // 按极角从小到大排序
    sort(points + 1, points + n, cmp);

    // 构建凸包
    stack<Point> hull;
    hull.push(points[0]);
    hull.push(points[1]);
    for (int i = 2; i < n; i++) {
        Point top = hull.top();
        hull.pop();
        while (hull.size() && cross_product(hull.top(), top, points[i]) <= 0) {
            top = hull.top();
            hull.pop();
        }
        hull.push(top);
        hull.push(points[i]);
    }

    // 输出凸包顶点
    while (!hull.empty()) {
        Point p = hull.top();
        cout << "(" << p.x << ", " << p.y << ")" << endl;
        hull.pop();
    }
}

int main() {
    Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};
    int n = sizeof(points) / sizeof(points[0]);
    convex_hull(points, n);
    return 0;
}

其中，`Point`结构体表示二维平面上的一个点，`dist_square`函数用于求出两点之间的距离平方，`cross_product`函数用于求出三点构成的向量的叉积，`cmp`函数用于排序，`convex_hull`函数实现了Graham Scan算法，`main`函数用于测试。