c语言编写：1.分别用蛮力法和分治法求解最近对问题 2.输人是平面上的N个点，输出是最近点对距离。 3.要求随机生成N个点的平面坐标。 4.分别对N=100，1000，3000，统计算法运行时间（微秒），分析算法的时间性能（提高）。

在C语言中，我们可以使用蛮力法（也称为暴力搜索）和分治法（如K-d树或最短路径算法）来解决最近点对问题。以下是简要描述：

1. **蛮力法**（Brute Force）：
- 输入：N个二维坐标 (x, y)
- 算法步骤：
a. 创建一个邻接矩阵或者一个包含所有点对距离的数组。
b. 遍历所有可能的点对，计算它们之间的欧几里得距离。
c. 找到最小的距离作为结果。
- 时间复杂度：O(N^2)，空间复杂度：O(N)

2. **分治法（例如K-d树）**：
- 输入：N个二维坐标
- K-d树是一种数据结构，用于快速查找最近邻。
- 算法步骤：
a. 构建K-d树，将点按照一个维度划分成两个子集。
b. 对每个子集递归地构建K-d树，然后找到当前子集中的最近点。
c. 比较这两个最近点之间的距离与已知最近距离。
- 时间复杂度：取决于实现细节，通常较低，接近O(log N)或O(N log N)。
- 空间复杂度：O(N)

为了实现这个需求：
- **随机生成N个点**：可以使用`srand(time(0))`初始化随机数种子，并通过`rand()`函数生成随机整数范围内的值，然后设置为坐标。

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

int generate_random(int min, int max) {
    return min + rand() % (max - min + 1);
}

void random_points(int N, double points[][2]) {
    srand(time(NULL));
    for (int i = 0; i < N; ++i) {
        points[i][0] = generate_random(0, MAX_X);
        points[i][1] = generate_random(0, MAX_Y);
    }
}

- **计算时间性能**：

   #include <sys/time.h> // For time measurement
   ...
   struct timeval start, end;
   long diff;

   gettimeofday(&start, NULL); // Start timer
   ... // Call your algorithm here (brute_force or kdtree)
   gettimeofday(&end, NULL); // Stop timer
   diff = (end.tv_sec - start.tv_sec) * 1000000L + end.tv_usec - start.tv_usec;
   printf("Algorithm runtime: %ld microseconds\n", diff);

对于N的不同值（100、1000、3000），你可以分别测量并记录下来，然后绘制图表比较算法在不同规模下的效率提升，通常随着N增大，分治法的优势会更明显。