JavaScrip求最近点对，使用分治法

JavaScript求解最近点对（Closest Pair of Points）通常采用的是分治算法，最常见的是使用二分查找结合排序的思想。这个问题可以转换为在一个有序数组中寻找两个元素，使得它们之间的曼哈顿距离（绝对值之和）最小。以下是基本步骤：

1. **数据预处理**：首先，你需要将给定的二维坐标点集合按x轴或y轴进行排序，因为两点间的曼哈顿距离与顺序有关。

2. **划分**：如果你有一个包含n个点的数组，你可以将其分为两半，对每半分别递归地找出最近点对。

3. **合并**：然后，在每半的结果中找到当前范围内最近的一对点，接着计算这对点与其他未匹配点的距离，更新全局最近点对的距离。这个过程可以用线性时间复杂度O(n)完成，因为你只需要遍历一次未匹配的点。

4. **返回结果**：当数组只剩下一个元素时，说明所有点都在同一组，直接返回这个点作为“最近点对”（假设它是原点）；否则，返回经过合并得到的最近点对。

function closestPair(points, sorted = false) {
    if (sorted || points.length <= 3) {
        // 对于小规模，可以直接遍历
        return furthestDistance(points);
    }
    
    const mid = Math.floor(points.length / 2);
    const left = closestPair(points.slice(0, mid), true);
    const right = closestPair(points.slice(mid), true);
    
    return findClosest(left, right);
}

// 辅助函数：在左右两部分中找最近点对
function findClosest(left, right) {
    let minDistance = Infinity;
    for (let i = 0; i < left.length; i++) {
        for (let j = 0; j < right.length; j++) {
            const distance = getManhattanDistance(left[i], right[j]);
            if (distance < minDistance) {
                minDistance = distance;
            }
        }
    }
    return minDistance;
}

其中`getManhattanDistance`是一个辅助函数，用于计算两点之间的曼哈顿距离。