c# - 一系列xy坐标中的最短距离

Question

我有一个作业，比较解决一个问题的 2 种不同算法。问题是:

假设我有一系列这样的 xy 坐标:

A(2,3), B(5,6), C(7,8), D(6,2), E(5,5)等。

我想找到 2 个坐标，它们之间的距离最短。一种解决方案是使用蛮力(将它们一一匹配)，但还有另一种解决方案使用“分而治之”的方法..

你能帮我用“分而治之”的方法吗？

Answer 1

递归分治法的工作原理如下:

1) Sort points according to their x-coordinates.
2) Split the set of points into two equal-sized subsets by a vertical line x=xmid.

3) Solve the problem recursively in the left and right subsets. This
yields the left-side and right-side minimum distances dLmin and dRmin, respectively.

4) Find the minimal distance dLRmin among the pair of points in which one point lies on the left of the dividing vertical and the second point lies to the right.

5) The final answer is the minimum among dLmin, dRmin, and dLRmin. (source)

它的复杂度为 O(n log n)。还有一个伪代码实现 here以及方法的可视化描述 here .