3.8给定n个点，其坐标为(x,y)(0≤i≤n-1),要求使用分治策略求解设计算法，找出其中距 离最近的两个点。两点间的距离公式为:√(x-x,)2+(y,-y,)2 特点以 (1)写出算法的伪代码; (2)编写C++程序实现这一算法; 而这些于 (3)分析算法的时间复杂度。

为了使用分治策略解决这个问题，我们可以设计一个递归的算法，其大致思路如下：

**算法的伪代码：**

function ClosestPair(points[], n):
    if n <= 2:            // 如果只剩下一个或没有点，直接返回当前点
        return points[0], points[1]

    // 将点集分为两半
    mid = n / 2
    left_points = ClosestPair(points[0...mid], mid)
    right_points = ClosestPair(points[mid...n-1], n - mid - 1)

    // 寻找左右两个子序列之间的最接近点对
    closest_left = find_closest(left_points[0], left_points[1])
    closest_right = find_closest(right_points[0], right_points[1])

    // 在整个序列中寻找全局最接近点对
    global_closest = compare(closest_left, closest_right)

    return global_closest

// 辅助函数：在两个点中找到最近的一对
function find_closest(pointA, pointB):
    distance = sqrt((pointA.x - pointB.x)^2 + (pointA.y - pointB.y)^2)
    return pointA, pointB if distance < other_distance else other_point, pointB

// 辅助函数：比较两个点对的距离并返回较近的那个
function compare(pair1, pair2):
    return pair1 if distance(pair1) < distance(pair2) else pair2

**C++ 实现：**

#include <vector>
#include <cmath>

struct Point {
    double x, y;

    // 计算两点间距离
    double distance_to(const Point& other) const {
        return std::sqrt(std::pow(x - other.x, 2) + std::pow(y - other.y, 2));
    }
};

Point ClosestPair(std::vector<Point>& points, int n) {
    // ... 与伪代码相同
}

int main() {
    // 初始化点集并调用ClosestPair函数
    std::vector<Point> points = {/* your points */};
    int n = points.size();
    Point closest_pair = ClosestPair(points, n);
    // 返回结果
    return 0;
}

**时间复杂度分析：**
这个算法使用了分治法，每一次分割都将问题规模减半。查找每个子序列内的最接近点对的时间复杂度是O(n)，而合并两个子序列以及在所有点中寻找全球最接近点对的时间复杂度也是O(n)。因此，总的时间复杂度是O(n log n)，其中log n来自于递归划分的过程。