最近点对问题：蛮力法与分治法实现及性能比较

一、实验题目

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

二、实验要求

分别用蛮力法和分治法求解最近对问题

输入是平面上的N个点，输出是最近点对距离。
要求随机生成N个点的平面坐标。
分别对N=100，1000，3000，统计算法运行时间(微秒)，分析算法的时间性能(提高)。

完成以上实验要求，并给出实验思路和实验总结，并分别给出相应的C语言代码和分别给出N=100，1000，3000的C语言代码内容：

实验思路：

1. 蛮力法：

遍历集合S中的每一对点，计算它们之间的距离。
找出距离最小的点对，即为最近点对。

2. 分治法：

将集合S按照x坐标进行排序。
将集合S分成两部分，分别为左边的点集L和右边的点集R。
递归地对点集L和R分别求解最近点对。
在L和R中分别找出距离最小的点对，记为dL和dR。
取dL和dR中距离较小的点对，记为d。
在S中找出以距离d为半径的两个区域内的点对中的最近点对，记为d'.
返回d和d'中距离较小的点对作为最近点对。

实验总结：

蛮力法的时间复杂度为O(n^2)，需要遍历所有点对进行距离计算。
分治法的时间复杂度为O(nlogn)，将点集分成两部分后递归求解。
分治法相对于蛮力法在大数据规模下有明显的时间优势。
通过随机生成n个点的平面坐标，可以对算法的时间性能进行分析和比较。

C语言代码实现：

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

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

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 points[], int n) {
    double minDist = INFINITY;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            double dist = distance(points[i], points[j]);
            if (dist < minDist) {
                minDist = dist;
            }
        }
    }
    return minDist;
}

double min(double x, double y) {
    return (x < y) ? x : y;
}

double stripClosest(Point strip[], int size, double d) {
    double minDist = d;
    for (int i = 0; i < size; i++) {
        for (int j = i+1; j < size && (strip[j].y - strip[i].y) < minDist; j++) {
            double dist = distance(strip[i], strip[j]);
            if (dist < minDist) {
                minDist = dist;
            }
        }
    }
    return minDist;
}

double closestUtil(Point points[], int n) {
    if (n <= 3) {
        return bruteForce(points, n);
    }
    
    int mid = n / 2;
    Point midPoint = points[mid];
    
    double dl = closestUtil(points, mid);
    double dr = closestUtil(points + mid, n - mid);
    
    double d = min(dl, dr);
    
    Point strip[n];
    int j = 0;
    for (int i = 0; i < n; i++) {
        if (abs(points[i].x - midPoint.x) < d) {
            strip[j] = points[i];
            j++;
        }
    }
    
    return min(d, stripClosest(strip, j, d));
}

double closest(Point points[], int n) {
    qsort(points, n, sizeof(Point), cmpX);
    return closestUtil(points, n);
}

int main() {
    srand(time(NULL));
    int n = 100;  // 或者1000, 3000
    
    Point points[n];
    for (int i = 0; i < n; i++) {
        points[i].x = (double)rand() / RAND_MAX;
        points[i].y = (double)rand() / RAND_MAX;
    }
    
    clock_t start, end;
    double cpu_time_used;
    
    start = clock();
    double minDist = closest(points, n);
    end = clock();
    
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    
    printf("Minimum distance: %f\n", minDist);
    printf("Time taken: %f seconds\n", cpu_time_used);
    
    return 0;
}