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

好的，以下是Graham-Scan算法的C++实现。

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

struct Point {
    int x, y;
};

// 叉积
int cross(const Point &a, const Point &b, const Point &c) {
    return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}

// 求凸包，返回点集
vector<Point> convexHull(vector<Point> &points) {
    int n = points.size();
    // 先按照x坐标从小到大排序，x坐标相同按y坐标从小到大排序
    sort(points.begin(), points.end(), [](const Point &a, const Point &b) {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    });
    // 求下凸壳
    vector<Point> lower;
    for (int i = 0; i < n; ++i) {
        while (lower.size() >= 2 && cross(lower[lower.size() - 2], lower.back(), points[i]) <= 0)
            lower.pop_back();
        lower.push_back(points[i]);
    }
    // 求上凸壳
    vector<Point> upper;
    for (int i = n - 1; i >= 0; --i) {
        while (upper.size() >= 2 && cross(upper[upper.size() - 2], upper.back(), points[i]) <= 0)
            upper.pop_back();
        upper.push_back(points[i]);
    }
    // 合并下凸壳和上凸壳
    vector<Point> ans(lower);
    ans.insert(ans.end(), upper.begin() + 1, upper.end() - 1);
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; ++i)
        cin >> points[i].x >> points[i].y;
    vector<Point> hull = convexHull(points);
    cout << "Convex Hull:" << endl;
    for (const Point &p : hull)
        cout << p.x << " " << p.y << endl;
    return 0;
}

在上述代码中：
- `Point` 结构体表示一个点，包含 `x` 和 `y` 坐标；
- `cross` 函数用于计算向量 $\overrightarrow{AB}$ 和 $\overrightarrow{AC}$ 的叉积，即 $(\overrightarrow{AB} \times \overrightarrow{AC})$，结果为正表示 $\overrightarrow{AB}$ 在 $\overrightarrow{AC}$ 的逆时针方向，结果为负表示 $\overrightarrow{AB}$ 在 $\overrightarrow{AC}$ 的顺时针方向，结果为 $0$ 表示 $\overrightarrow{AB}$ 与 $\overrightarrow{AC}$ 共线；
- `convexHull` 函数用于求解凸包，输入为点集 `points`，输出为凸包点集；
- 在函数内部，先按照 x 坐标从小到大排序，x 坐标相同按 y 坐标从小到大排序；
- 接着求下凸壳，利用单调栈维护；
- 再求上凸壳，同样利用单调栈维护；
- 最后将下凸壳和上凸壳合并，得到最终的凸包点集。

希望能对你有所帮助。