最近点对问题-分治法C语言算法代码

最近点对问题（Closest Pair of Points）通常是指在一个二维数组（点集）中找到两个点，它们之间的曼哈顿距离（两点横坐标之差的绝对值加上纵坐标之差的绝对值）最小的问题。这是一种经典的计算机科学问题，可以使用分治法解决。

以下是使用C语言的一个简单分治法的递归解决方案：

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

// 计算两点之间的曼哈顿距离
int manhattanDistance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

// 分治函数，查找给定区间内的最接近的点对
void closestPairHelper(int left, int right, int points[], int n, int* minDist, int** pair) {
    if (left == right) { // 如果只有一个元素，直接返回
        *pair = &points[left];
        *minDist = INT_MAX;
        return;
    }

    int mid = (left + right) / 2;
    int dist1 = INT_MAX, dist2 = INT_MAX;

    // 对左半部分和右半部分分别计算最接近的点对
    closestPairHelper(left, mid, points, n, &dist1, pair);
    closestPairHelper(mid + 1, right, points, n, &dist2, pair);

    // 更新结果
    if (dist1 < dist2 || dist1 == dist2 && manhattanDistance(points[mid][0], points[mid][1], points[left][0], points[left][1]) < dist2) {
        *minDist = dist1;
        *pair = &points[left];
    } else {
        *minDist = dist2;
        *pair = &points[mid+1];
    }
}

// 主函数，调用辅助函数并处理输入数据
void closestPair(int points[], int n) {
    int minDist = INT_MAX, *pair = NULL;
    closestPairHelper(0, n - 1, points, n, &minDist, &pair);
    printf("Minimum Manhattan distance: %d\n", minDist);
    printf("Points with minimum distance: (%d, %d), (%d, %d)\n", pair->x, pair->y, points[(*pair)->y].x, points[(*pair)->y].y);
}

int main() {
    int points[] = {{1, 3}, {2, 4}, {3, 5}, {4, 6}, {5, 7}};
    int n = sizeof(points) / sizeof(points[0]);

    closestPair(points, n);

    return 0;
}

这个程序首先将点集分为两半，然后递归地查找每一半的最接近点对。最后，它比较左右两边的结果，并选择最接近的那个点对作为最终答案。