凸包问题-graham-scan算法c++实现

好的，以下是 Graham-Scan 算法的 C++ 实现，用于求解凸包问题：

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x, y;
};

// 按照 x 坐标从小到大排序，若 x 坐标相等，则按照 y 坐标从小到大排序。
bool cmp(Point a, Point b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

// 计算叉积。
int cross(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 算法求解凸包。
vector<Point> grahamScan(vector<Point> &points) {
    int n = points.size();
    if (n <= 1) return points;

    sort(points.begin(), points.end(), cmp);

    vector<Point> hull(2 * n);
    int k = 0;

    // 构建下凸壳。
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(hull[k - 2], hull[k - 1], points[i]) <= 0) k--;
        hull[k++] = points[i];
    }

    // 构建上凸壳。
    for (int i = n - 2, t = k + 1; i >= 0; --i) {
        while (k >= t && cross(hull[k - 2], hull[k - 1], points[i]) <= 0) k--;
        hull[k++] = points[i];
    }

    // 去除重复点。
    hull.resize(k - 1);
    return hull;
}

int main() {
    // 测试数据。
    vector<Point> points = {{0, 3}, {1, 1}, {2, 2}, {4, 4},
                            {0, 0}, {1, 2}, {3, 1}, {3, 3}};

    vector<Point> hull = grahamScan(points);

    // 输出凸包的顶点。
    for (int i = 0; i < hull.size(); ++i) {
        cout << "(" << hull[i].x << ", " << hull[i].y << ")" << endl;
    }

    return 0;
}

注意点：

1. 为了方便起见，我直接使用了 C++11 的新特性，使用 vector 存储点集，如果你使用的是较老的编译器，可以使用数组代替 vector。
2. 实现中为了方便起见，我使用了三个点 $A(a_x,a_y)$、$B(b_x,b_y)$、$C(c_x,c_y)$ 的叉积 $cross(A,B,C)$ 表示向量 $\vec{AB}$ 和 $\vec{AC}$ 的叉积。当叉积 $cross(A,B,C)>0$ 时，表示 $\vec{AB}$ 在 $\vec{AC}$ 的逆时针方向；当叉积 $cross(A,B,C)<0$ 时，表示 $\vec{AB}$ 在 $\vec{AC}$ 的顺时针方向；当叉积 $cross(A,B,C)=0$ 时，表示 $\vec{AB}$ 和 $\vec{AC}$ 共线。
3. 为了避免精度误差，最好使用整数类型存储坐标，如 int 类型。