图算法太难懂？凸包算法搞不通？看这篇文章就够了

标题：你以为凸包算法只是数学游戏？不，这才是竞赛中的制胜法宝！

你以为几何算法只是竞赛中的小儿科，顶多画个漂亮图形？但是，朋友，你要知道，如果你还停留在这样的认知，那你已经out了！凸包（Convex Hull）——听起来像个不起眼的小问题，但实际上，它是算法竞赛中的核武器，是能让你在众多参赛者中脱颖而出的绝技！很多人觉得这个算法不过就是点和线的简单组合，真正复杂的东西不在这里。但真的是如此吗？其实，凸包算法不仅是计算几何的基础，也是深入理解算法优化和空间复杂度的绝佳案例。今天，我们就要来掰开揉碎了，深入浅出地揭开这些经典算法的神秘面纱！

什么是凸包？一听名字就知道不简单！

在二维平面上，给你一堆点，你能画出一个“包”裹住这些点的最小凸多边形吗？这就是所谓的凸包问题。你或许以为这没什么大不了的，但试想一下，应用场景遍布图像处理、机器人路径规划、数据分析中的聚类问题等等，简直就是无所不在！你在算法竞赛中遇到的复杂度都离不开这几个字：凸包。

那么问题来了，如何高效地找到这个“包”？在计算几何的世界里，有几种经典的算法——Graham 扫描法（Graham Scan）、Jarvis March（礼花算法）、Andrew’s Monotone Chain（单调链），每一个名字听起来都那么高大上，但今天我们只挑最具代表性的两种——Graham 扫描法和礼花算法，细细道来，帮你轻松攻克！

1. Graham 扫描法：每一个步骤都堪称艺术品的算法

Graham 扫描法（Graham Scan），一个听起来像科学家的名字，其实是算法中的“艺术家”。它将凸包问题转换成了一个排序问题——用时间复杂度 (O(n \log n)) 的复杂度来搞定一切。这就是聪明人的做法，聪明在哪里？就在于，它利用了极角排序和栈结构的妙用，让你在构建凸包的过程中不断找到“最优解”。

步骤分析：一步一步走上“巅峰”

1. 找到最低且最左的点（起点）：
   你以为随便找个点就行？不！最低且最左的点才是你成功的基石。这个点一定在凸包上，不信？数学定理摆在那里，绝对错不了！

2. 按极角排序：给点们排排队，按顺序来：
   把剩下的点按照与起点的极角从小到大排序。这里要注意了，排序可是精髓中的精髓！极角排序是这个算法的灵魂，搞定这个，你就成功了一半。

3. 遍历点集构建凸包：要有耐心，急不得！：
   开始用栈来维护我们的凸包顶点，遇到“向左转”的点就压入栈中，遇到“向右转”的点就弹出栈顶。搞不清楚左右？没关系，叉积公式给你撑腰！这个过程就像是在锻造一块完美的宝石，耐心打磨，成品就是惊艳的。

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

typedef struct {
    double x, y;
} Point;

// 计算两点之间的极角（atan2）
double polar_angle(Point p0, Point p1) {
    return atan2(p1.y - p0.y, p1.x - p0.x);
}

// 计算两向量的叉积
double cross_product(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// 比较函数，用于按极角排序点
int compare_points(const void *a, const void *b, void *origin) {
    Point *p0 = (Point *)origin;
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;
    double angle1 = polar_angle(*p0, *p1);
    double angle2 = polar_angle(*p0, *p2);

    if (angle1 < angle2) return -1;
    if (angle1 > angle2) return 1;

    double dist1 = (p1->x - p0->x) * (p1->x - p0->x) + (p1->y - p0->y) * (p1->y - p0->y);
    double dist2 = (p2->x - p0->x) * (p2->x - p0->x) + (p2->y - p0->y) * (p2->y - p0->y);

    return (dist1 < dist2) ? -1 : 1;
}

// 求解凸包的Graham扫描算法
void graham_scan(Point points[], int n, Point hull[], int *hull_size) {
    // 找到最低且最左的点作为起点
    int min_index = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].y < points[min_index].y || 
            (points[i].y == points[min_index].y && points[i].x < points[min_index].x)) {
            min_index = i;
        }
    }

    Point temp = points[0];
    points[0] = points[min_index];
    points[min_index] = temp;

    qsort_r(points + 1, n - 1, sizeof(Point), compare_points, &points[0]);

    int top = 1;
    hull[0] = points[0];
    hull[1] = points[1];

    for (int i = 2; i < n; i++) {
        while (top > 0 && cross_product(hull[top - 1], hull[top], points[i]) <= 0) {
            top--;
        }
        hull[++top] = points[i];
    }

    *hull_size = top + 1;
}

// 测试用例
int main() {
    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};
    int n = sizeof(points) / sizeof(points[0]);
    Point hull[n];
    int hull_size;

    graham_scan(points, n, hull, &hull_size);

    printf("凸包点:\n");
    for (int i = 0; i < hull_size; i++) {
        printf("(%.1f, %.1f)\n", hull[i].x, hull[i].y);
    }

    return 0;
}

看完代码，是不是有点豁然开朗的感觉？这就是Graham扫描法的魅力——简洁而不简单，强大又优雅。

2. Jarvis March（礼花算法）：简单但不平凡，天生的贪心策略

如果你以为算法世界里只要用上高级排序就能高枕无忧，那你就错了！Jarvis March，俗称“礼花算法”，是一种基于贪心思想的凸包算法。简单？可不要小看它！虽然时间复杂度为 (O(nh))，看起来效率不高，但在某些场景下却能出奇制胜！为什么？因为它的实现相当直观——从最左下角的点开始，每次都选择下一个能形成“最左转”的点，直到回到起始点。

代码实现：老少咸宜，通俗易懂

#include <stdio.h>

#define MAX_POINTS 100

typedef struct {
    double x, y;
} Point;

int orientation(Point p, Point q, Point r) {
    double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;
    return (val > 0) ? 1 : 2;
}

void jarvis_march(Point points[], int n) {
    if (n < 3) return;

    int hull[MAX_POINTS];
    int hull_size = 0;

    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;

    int p = l, q;
    do {
        hull[hull_size++] = p;
        q = (p + 1) % n;

        for (int i = 0; i < n; i++) {
           
            if (orientation(points[p], points[i], points[q]) == 2) {
                q = i;
            }
        }

        p = q;
    } while (p != l);

    printf("凸包点:\n");
    for (int i = 0; i < hull_size; i++) {
        printf("(%.1f, %.1f)\n", points[hull[i]].x, points[hull[i]].y);
    }
}

// 测试用例
int main() {
    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};
    int n = sizeof(points) / sizeof(points[0]);

    jarvis_march(points, n);

    return 0;
}

看，这就是贪心策略的直接应用！代码简单易懂，却不失优雅。对于需要快速入门的同学来说，Jarvis March 是一个非常好的起步选择。

总结：凸包算法远不止于“点与线”的游戏

很多人以为几何算法仅仅是个“点与线”的游戏，但真正的高手都知道，算法的每一步都有其数学和编程的深意。从 Graham 扫描法的极角排序到 Jarvis March 的贪心选择，每一种方法都是从问题的本质出发，探索更高效的解法。掌握这些算法，你不仅能轻松应对各种竞赛题目，还能在面试中赢得面试官的青睐！所以，不要再认为几何算法只是学术游戏了，它们可是你打开算法之门的钥匙！

还不赶快动手试试？今天的分享就到这里，我们下次见！