凸包问题c语言蛮力法

凸包问题是计算几何学中的经典问题，它的主要目标是找到一个点集的最小凸包，即这个点集的最小凸多边形。蛮力法是解决凸包问题的一种基本算法，其时间复杂度为 O(n^3)，在实际应用中，其效率较低。

下面是C语言蛮力法求解凸包问题的基本思路：

1. 首先，需要定义一个存储点坐标的结构体类型，如下所示：

typedef struct {
    int x;
    int y;
} Point;

2. 然后，需要输入点的数量和点的坐标，将其存储到一个数组中。

int n; // 点的数量
Point points[MAXN]; // 存储点坐标的数组

scanf("%d", &n);
for (int i = 0; i < n; i++) {
    scanf("%d%d", &points[i].x, &points[i].y);
}

3. 接下来，需要枚举所有可能的凸包顶点，对于每个顶点，遍历所有点，判断是否在该凸包内。

int ans = 0; // 记录凸包顶点数量
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        int cnt = 2; // 当前凸包顶点数量
        for (int k = 0; k < n; k++) {
            if (k == i || k == j) continue; // 排除已确定的顶点
            if (judge(points[i], points[j], points[k])) { // 判断是否在凸包内
                cnt++;
            }
        }
        ans = max(ans, cnt);
    }
}
printf("%d\n", ans);

4. 最后，需要实现一个判断点是否在凸包内的函数，可以使用叉积计算法。

bool judge(Point a, Point b, Point c) {
    return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) >= 0;
}