用C语言设计求解平面最邻近点对算法 ：数据没有事先预排序，设计算法O(n(logn)2)；数据事先预排序，设计算法O(nlogn)，所有数据随机生成两个文件，从文件读入数据。

平面最邻近点对算法解决的问题是在平面上给定n个点，找出距离最近的两个点。其中，距离可以用欧几里得距离来衡量。

算法设计：

1. 数据没有事先预排序：

（1）首先读入所有的点，并保存在一个数组中；

（2）将所有的点按照横坐标排序；

（3）使用分治法，将点集分为左右两个部分；

（4）递归地在左右两个部分中分别求出最小距离；

（5）然后考虑跨越两个部分的情况，找到跨越两个部分的最小距离。

（6）返回最小距离。

2. 数据事先预排序：

（1）首先读入所有的点，并保存在一个数组中；

（2）将所有的点按照横坐标排序；

（3）使用分治法，将点集分为左右两个部分；

（4）递归地在左右两个部分中分别求出最小距离；

（5）然后考虑跨越两个部分的情况，找到跨越两个部分的最小距离。

（6）返回最小距离。

时间复杂度：

（1）数据没有事先预排序：由于需要对所有点进行排序，时间复杂度为O(nlogn)，而每次递归需要O(n)的时间，因此最终的时间复杂度为O(n(logn)2)。

（2）数据事先预排序：由于数据已经预排序，因此每次递归需要O(n)的时间，因此最终的时间复杂度为O(nlogn)。

代码实现：

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

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

int cmp_x(const void* a, const void* b) {
    double x1 = ((Point*)a)->x, x2 = ((Point*)b)->x;
    if (x1 < x2) return -1;
    else if (x1 > x2) return 1;
    else return 0;
}

int cmp_y(const void* a, const void* b) {
    double y1 = ((Point*)a)->y, y2 = ((Point*)b)->y;
    if (y1 < y2) return -1;
    else if (y1 > y2) return 1;
    else return 0;
}

double dist(Point p1, Point p2) {
    double dx = p1.x - p2.x, dy = p1.y - p2.y;
    return sqrt(dx * dx + dy * dy);
}

double min(double a, double b) {
    return a < b ? a : b;
}

double closest_pair(Point* p, int n) {
    if (n <= 1) return INFINITY;
    int m = n / 2;
    double x = p[m].x;
    double d = min(closest_pair(p, m), closest_pair(p + m, n - m));
    qsort(p, n, sizeof(Point), cmp_y);
    Point* b = (Point*)malloc(n * sizeof(Point));
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (fabs(p[i].x - x) < d) {
            for (int j = k - 1; j >= 0 && p[i].y - b[j].y < d; j--) {
                d = min(d, dist(p[i], b[j]));
            }
            b[k++] = p[i];
        }
    }
    free(b);
    return d;
}

int main() {
    int n;
    printf("请输入点的数量：");
    scanf("%d", &n);
    Point* p = (Point*)malloc(n * sizeof(Point));
    FILE* fp1 = fopen("input1.txt", "w");
    FILE* fp2 = fopen("input2.txt", "w");
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        p[i].x = rand() % 100;
        p[i].y = rand() % 100;
        fprintf(fp1, "%.2lf %.2lf\n", p[i].x, p[i].y);
    }
    qsort(p, n, sizeof(Point), cmp_x);
    for (int i = 0; i < n; i++) {
        fprintf(fp2, "%.2lf %.2lf\n", p[i].x, p[i].y);
    }
    fclose(fp1);
    fclose(fp2);
    double d1 = closest_pair(p, n);
    printf("数据没有事先预排序，最邻近点对的距离为：%.2lf\n", d1);
    double d2;
    fp2 = fopen("input2.txt", "r");
    for (int i = 0; i < n; i++) {
        fscanf(fp2, "%lf%lf", &p[i].x, &p[i].y);
    }
    fclose(fp2);
    d2 = closest_pair(p, n);
    printf("数据已经事先预排序，最邻近点对的距离为：%.2lf\n", d2);
    free(p);
    return 0;
}