C语言实现分治法求解最近点对问题

一、实验题目

设p1=(x1, y1), p2=(x2, y2), ..., pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。

二、实验要求

输入是平面上的N个点，输出是最近点对的距离。
随机生成N个点的平面坐标。
分别对N=100，1000，3000进行实验，并统计算法的运行时间。
分析算法的时间性能。

三、C语言代码

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

// 定义点结构体
typedef struct {
    int x;
    int y;
} Point;

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

// 比较函数，用于快速排序
int compare(const void* a, const void* b) {
    Point* p1 = (Point*)a;
    Point* p2 = (Point*)b;
    return p1->x - p2->x;
}

// 分治法找出最近点对
double closestPair(Point* points, int left, int right) {
    // 如果只有两个点，直接返回它们的距离
    if (right - left == 1) {
        return distance(points[left], points[right]);
    }
    // 如果只有一个点，返回无穷大
    if (right == left) {
        return INFINITY;
    }

    // 分治法求解最近点对距离
    int mid = (left + right) / 2;
    double d1 = closestPair(points, left, mid);
    double d2 = closestPair(points, mid + 1, right);
    double d = fmin(d1, d2);

    // 找出距离中线小于d的点
    Point strip[right - left + 1];
    int j = 0;
    for (int i = left; i <= right; i++) {
        if (abs(points[i].x - points[mid].x) < d) {
            strip[j++] = points[i];
        }
    }

    // 按照纵坐标排序
    qsort(strip, j, sizeof(Point), compare);

    // 在纵坐标方向上寻找最近点对
    for (int i = 0; i < j; i++) {
        for (int k = i + 1; k < j && (strip[k].y - strip[i].y) < d; k++) {
            double dist = distance(strip[i], strip[k]);
            if (dist < d) {
                d = dist;
            }
        }
    }

    return d;
}

int main() {
    int N = 100; // 点的个数
    Point points[N];

    // 随机生成N个点的坐标
    srand(time(NULL));
    for (int i = 0; i < N; i++) {
        points[i].x = rand() % 1000;
        points[i].y = rand() % 1000;
    }

    // 按照横坐标排序
    qsort(points, N, sizeof(Point), compare);

    // 调用最近点对算法
    double closestDistance = closestPair(points, 0, N - 1);

    printf("最近点对的距离为：%lf\n", closestDistance);

    return 0;
}

以上是一个使用分治法求解最近点对问题的C语言代码。代码中使用了快速排序算法对点进行排序，然后使用分治法求解最近点对的距离。实验中可以根据需要修改点的个数N，并统计算法的运行时间。