c语言凸包问题并输出边界上的点

在计算几何中，凸包问题是一个经典的算法问题，它旨在找到一个包含一组二维点的最小凸多边形，使得所有给定点都位于多边形的边界上或内部。这个多边形称为凸包，它的一个重要特性是任意三个顶点不会共线，并且凸包上的任意两点之间的线段都会位于凸包内部。

在C语言中，实现凸包问题的一种常见算法是Graham扫描法。其基本步骤如下：
1. 找到给定点集中纵坐标最小的点，如果有多个这样的点，则取横坐标最小的一个，作为起始点。
2. 根据所有点相对于起始点的极角进行排序，如果极角相同，则去除重复的点。
3. 从排序后的点集中依次取出点，按照顺序构建凸包。每次取出一个点时，检查这个点和凸包中最后两个顶点构成的三角形，如果这个三角形的内部包含了凸包上当前顶点，则将最后一个顶点删除，以此类推，直到找到一个合适的顶点加入到凸包中。
4. 继续这个过程直到所有点都被处理过，此时得到的点集就是凸包的顶点。

在C语言中，为了存储凸包的边界上的点，我们通常会使用栈（Stack）这种数据结构，因为Graham扫描法本质上是一个栈操作过程。

以下是使用C语言实现Graham扫描法的简单示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define N 100

typedef struct {
    double x, y;
} Point;

int compare(const void *a, const void *b) {
    Point *p1 = (Point *)a, *p2 = (Point *)b;
    double dx1 = p1->x - base.x, dy1 = p1->y - base.y;
    double dx2 = p2->x - base.x, dy2 = p2->y - base.y;
    if (fabs(dy1) > fabs(dy2))
        return (dy1 > dy2) ? 1 : -1;
    else if (fabs(dy1) < fabs(dy2))
        return (dy1 > dy2) ? 1 : -1;
    else if (dx1 > dx2)
        return -1;
    else if (dx1 < dx2)
        return 1;
    else
        return 0;
}

Point stack[N], hull[N];
int top = -1;

void push(Point p) {
    stack[++top] = p;
}

Point pop() {
    return stack[top--];
}

int graham_scan(Point points[], int n) {
    int m = 0;
    qsort(points, n, sizeof(Point), compare);
    for (int i = 0; i < n; i++) {
        while (m > 1 && crossProduct(hull[m-2], hull[m-1], points[i]) <= 0)
            pop();
        push(points[i]);
    }
    return m;
}

int main() {
    // 假设points数组已经填充了n个点
    // Point points[N];
    // int n = ... // 点的数量
    // ... // 初始化points数组
    int m = graham_scan(points, n);
    // 输出凸包上的点
    for (int i = 0; i < m; i++) {
        printf("Point: (%f, %f)\n", hull[i].x, hull[i].y);
    }
    return 0;
}

double crossProduct(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

请注意，上述代码是一个简化的示例，用于说明如何使用Graham扫描法求解凸包问题。在实际应用中，需要对边界情况进行更多检查和处理。