设P={(x 1 ​ ,y 1 ​ ),(x 2 ​ ,y 2 ​ ),⋯,(x n ​ ,y n ​ )}是平面上散列的n个点的集合。请编写程序找出集合中距离最近的点对。严格地说，相同距离的最近点对可能不止一对，为了简单期间只找出第一对最近点对即可。c语言

以下是用C语言实现最近点对问题的代码，使用了分治法，时间复杂度为O(nlogn)。

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

typedef struct {
    double x;
    double y;
} Point;

// 按照x坐标从小到大排序
int cmp(const void *a, const void *b) {
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;
    if (p1->x < p2->x) {
        return -1;
    } else if (p1->x > p2->x) {
        return 1;
    } else {
        return 0;
    }
}

// 计算两点之间的距离
double distance(Point p1, Point p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx*dx + dy*dy);
}

// 暴力求解最近点对，用于递归到小规模问题
double bruteForce(Point p[], int n, int *p1, int *p2) {
    double minDist = distance(p[0], p[1]);
    *p1 = 0;
    *p2 = 1;
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n; j++) {
            double dist = distance(p[i], p[j]);
            if (dist < minDist) {
                minDist = dist;
                *p1 = i;
                *p2 = j;
            }
        }
    }
    return minDist;
}

// 分治求解最近点对
double closestPair(Point p[], int n, int *p1, int *p2) {
    if (n <= 3) {
        return bruteForce(p, n, p1, p2);
    }
    int mid = n / 2;
    Point midPoint = p[mid];
    int leftP1, leftP2, rightP1, rightP2;
    double leftDist = closestPair(p, mid, &leftP1, &leftP2);
    double rightDist = closestPair(p+mid, n-mid, &rightP1, &rightP2);
    double minDist = fmin(leftDist, rightDist);
    if (minDist == leftDist) {
        *p1 = leftP1;
        *p2 = leftP2;
    } else {
        *p1 = rightP1 + mid;
        *p2 = rightP2 + mid;
    }
    // 找出分界线两侧距离中心点小于最小距离的点
    int count = 0;
    Point strip[n];
    for (int i = 0; i < n; i++) {
        if (fabs(p[i].x - midPoint.x) < minDist) {
            strip[count++] = p[i];
        }
    }
    // 在跨越分界线的点中找到最近点对
    for (int i = 0; i < count-1; i++) {
        for (int j = i+1; j < count && j < i+8; j++) {
            double dist = distance(strip[i], strip[j]);
            if (dist < minDist) {
                minDist = dist;
                *p1 = i;
                *p2 = j;
            }
        }
    }
    return minDist;
}

int main() {
    int n;
    printf("请输入点的个数：");
    scanf("%d", &n);
    Point p[n];
    for (int i = 0; i < n; i++) {
        printf("请输入第%d个点的坐标(x,y)：", i+1);
        scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    qsort(p, n, sizeof(Point), cmp);
    int p1, p2;
    double minDist = closestPair(p, n, &p1, &p2);
    printf("距离最近的点对为(%lf,%lf)和(%lf,%lf)，距离为%lf\n", p[p1].x, p[p1].y, p[p2].x, p[p2].y, minDist);
    return 0;
}