C语言最近点对算法详解（分治法高效求解平面最近点对问题）

暴力解法 vs 分治法

最直观的方法是：计算所有点对之间的距离，取最小值。但这种方法需要比较 C(n,2) = n(n-1)/2 次，效率低下。

而分治法的核心思想是“分而治之”：

1. 将点集按 x 坐标排序；
2. 用一条垂直线将点集分成左右两半；
3. 递归地在左右两部分中分别求出最近点对距离 d₁ 和 d₂；
4. 取 d = min(d₁, d₂)；
5. 检查跨越中线的点对，是否存在距离小于 d 的点对。

关键在于第5步：我们只需检查中线两侧宽度为 d 的带状区域内、且 y 坐标相近的点。数学上可以证明，每个点最多只需与后面7个点比较即可！这大大减少了比较次数。

C语言算法实现

下面是一个完整的 C语言最近点对算法 实现，包含详细注释：

#include <stdio.h>#include <stdlib.h>#include <math.h>// 定义点结构体struct Point {    double x, y;};// 计算两点间欧氏距离double dist(struct Point p1, struct Point p2) {    return sqrt((p1.x - p2.x) * (p1.x - p2.x) +                 (p1.y - p2.y) * (p1.y - p2.y));}// 按x坐标比较函数（用于qsort）int compareX(const void* a, const void* b) {    struct Point *p1 = (struct Point*)a;    struct Point *p2 = (struct Point*)b;    return (p1->x > p2->x) - (p1->x < p2->x);}// 按y坐标比较函数int compareY(const void* a, const void* b) {    struct Point *p1 = (struct Point*)a;    struct Point *p2 = (struct Point*)b;    return (p1->y > p2->y) - (p1->y < p2->y);}// 暴力法（用于小规模点集）double bruteForce(struct Point P[], int n) {    double min = dist(P[0], P[1]);    for (int i = 0; i < n; ++i)        for (int j = i + 1; j < n; ++j)            if (dist(P[i], P[j]) < min)                min = dist(P[i], P[j]);    return min;}// 找出strip中最近点对double stripClosest(struct Point strip[], int size, double d) {    double min = d;    qsort(strip, size, sizeof(struct Point), compareY);        for (int i = 0; i < size; ++i)        for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min; ++j)            if (dist(strip[i], strip[j]) < min)                min = dist(strip[i], strip[j]);        return min;}// 主递归函数double closestUtil(struct Point Px[], struct Point Py[], int n) {    if (n <= 3)        return bruteForce(Px, n);        int mid = n / 2;    struct Point midPoint = Px[mid];        // 将Py分为左右两部分    struct Point Pyl[mid];    struct Point Pyr[n - mid];    int li = 0, ri = 0;    for (int i = 0; i < n; i++) {        if (Py[i].x <= midPoint.x)            Pyl[li++] = Py[i];        else            Pyr[ri++] = Py[i];    }        double dl = closestUtil(Px, Pyl, mid);    double dr = closestUtil(Px + mid, Pyr, n - mid);        double d = (dl < dr) ? dl : dr;        // 构建strip    struct Point strip[n];    int j = 0;    for (int i = 0; i < n; i++)        if (abs(Py[i].x - midPoint.x) < d)            strip[j] = Py[i], j++;        return stripClosest(strip, j, d);}// 入口函数double closest(struct Point P[], int n) {    struct Point Px[n];    struct Point Py[n];    for (int i = 0; i < n; i++) {        Px[i] = P[i];        Py[i] = P[i];    }        qsort(Px, n, sizeof(struct Point), compareX);    qsort(Py, n, sizeof(struct Point), compareY);        return closestUtil(Px, Py, n);}// 测试主函数int main() {    struct Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};    int n = sizeof(P) / sizeof(P[0]);        printf("The smallest distance is %.6f\n", closest(P, n));    return 0;}

代码说明

• compareX 和 compareY 用于对点按 x 或 y 坐标排序；
• bruteForce 在点数 ≤ 3 时直接暴力计算；
• stripClosest 处理跨越中线的点对，只检查 y 差小于当前最小距离的点；
• 主函数 closest 预先对点集按 x 和 y 排序，避免递归中重复排序。

总结

通过本教程，你已经掌握了如何用 C语言算法实现 高效的最近点对求解。分治法不仅提升了效率，也展示了算法设计的优雅。记住，理解问题本质比死记代码更重要。你可以尝试修改点集、添加输出最近点对的功能，或将其封装成库函数。

希望这篇关于 C语言最近点对算法 的教程对你有帮助！如果你觉得有用，欢迎分享给其他学习者。