algorithm - 最短距离对与线上给出的点？

有人能提出一个算法来找出未排序的共线点的最短距离对吗？
我有一个解决方案，在O（nlogn）中，只需做closest pair of points in 2D并应用到该行即可然而，这能更有效地做到吗？

最佳答案

请注意，您始终可以通过执行旋转变换将二维情况减少到一维情况。
不幸的是，我认为在一般情况下你不能做得比o（nlogn）好。最好的选择是对它们进行排序，然后遍历列表。