用蛮力法求凸包问题C++

用蛮力法（也称为暴力法或穷举法）求解凸包问题是指对一组点进行遍历，逐步添加每个点到当前已知的凸包上，直到所有点都被考虑过。这个过程通常用于二维空间内的点集。以下是使用C++实现的简单步骤：

1. 定义一个结构体或类存储点的坐标，比如Point，包含x和y成员变量。

struct Point {
    int x;
    int y;
};

2. 初始化一个最小凸包，可以是一个空集合，或者将第一个点作为初始顶点。

3. 对于剩余的所有点：
a. 检查每个点是否在当前凸包外部。如果不在，则更新凸包，可能需要增加新的边（连接现有的顶点和当前点）。
b. 可能的情况有三种：该点在左侧、上方或右侧形成一个新的三角形区域，这时分别检查新加入的线段是否完整地包围了其余点。
c. 更新凸包的边界，可能需要调整顶点列表，确保始终是最小化边的数量表示的凸包。

4. 最终剩下的顶点就构成了凸包。这里需要注意的是，算法的时间复杂度较高，对于大规模数据集效率较低，因为O(n^2)的操作次数。

以下是一个简化版的C++代码片段：

#include <vector>
using namespace std;

vector<Point> getConvexHull(vector<Point>& points) {
    sort(points.begin(), points.end(), [](const Point& p1, const Point& p2) { return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x; });
    vector<Point> hull(points[0], points.back());
    for (int i = 1; i + 1 < points.size(); ++i) {
        while (hull.size() >= 2 && crossProduct(hull[hull.size() - 2], hull.back(), points[i]) <= 0)
            hull.pop_back();
        hull.push_back(points[i]);
    }
    return hull;
}

// 辅助函数计算两个向量的叉积
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);
}