我目前被分配创建一个 c++ 程序来查找 (x,y) 坐标系中最近的一对点。但是，我在试图理解一件事时遇到了很多麻烦。
我读过的关于最近对问题的每个教程/指南都告诉我按 Y 坐标对点集进行排序，但我不明白这是什么意思？有人可以向我解释为什么我们按 Y 坐标对其进行排序，它的用途是什么？我知道我们按 X 对点进行排序以获得 L 和 X*，但我只是不明白为什么我们也必须按 Y 坐标对点进行排序。
问问题
345 次
1 回答
0
你没有，但是你的运行时间并没有超过 O(n 2 )。重点是尽可能少地计算——通过检查尽可能少的点，忽略那些你知道不会成为答案的部分。通过对 Y 进行排序来做到这一点。
这是我刚刚用谷歌搜索的一个很好的解释：http ://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html
于 2015-11-16T02:29:30.243 回答