用C语言解决最近点对问题-分治法 要代码

在C语言中，可以使用分治法解决最近点对问题（Closest Pair of Points Problem），通常用于二维坐标系中的点集，找到其中两个距离最短的点对。这里是一个基本的分治算法示例，它将问题分解为更小规模的子问题，并递归地寻找解：

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

// 计算两点之间的欧几里得距离
double distance(int x1, int y1, int x2, int y2) {
    return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

// 最近点对函数：分治法实现
void closestPair(int arr[], int low, int high) {
    if (low >= high)
        return;

    // 找到中间索引
    int mid = (low + high) / 2;

    // 分别处理左半部分、右半部分以及交叉区间
    double minDistance = INT_MAX;
    for (int i = low; i <= mid; i++) {
        for (int j = mid + 1; j <= high; j++) {
            double dist = distance(arr[i], arr[j]);
            if (dist < minDistance) {
                minDistance = dist;
            }
        }
    }

    // 对左半部分和右半部分分别调用closestPair
    closestPair(arr, low, mid);
    closestPair(arr, mid + 1, high);

    // 更新全局最小距离
    for (int i = low; i <= mid; i++) {
        for (int j = mid + 1; j <= high; j++) {
            if (distance(arr[i], arr[j]) < minDistance) {
                minDistance = distance(arr[i], arr[j]);
                // 更新对应的最近点对坐标
                printf("Found pair (%d,%d) and (%d,%d) with distance %f\n", 
                       arr[i], arr[j], arr[i], arr[j], minDistance);
            }
        }
    }
}

int main() {
    int n;
    printf("Enter the number of points: ");
    scanf("%d", &n);
    
    int points[n][2]; // 假设每个点是(x,y)形式
    for (int i = 0; i < n; i++) {
        printf("Enter point %d coordinates: ", i+1);
        scanf("%d %d", &points[i][0], &points[i][1]);
    }

    closestPair(points[0], 0, n-1);
    return 0;
}

这个程序首先读取输入的点集合，然后通过递归地分割数组并查找每部分内的最小距离，最后合并结果找出全局的最小距离和对应点对。