这是我前段时间在面试中问到的一个问题。而且我仍然不知道明智的答案。

问题是：

给定点集（x，y）。找到2个最远的点。彼此相距遥远。

例如，对于点：（0,0），（1,1），（-8、5）-最远的是：（1,1）和（-8,5），因为它们之间的距离大于（0,0）-（1,1）和（0,0）-（-8,5）。

一种明显的方法是计算所有点之间的所有距离，并找到最大值。问题在于它是O（n ^ 2），这对于大型数据集而言非常昂贵。

有一种方法是先在边界上跟踪点，然后为它们计算距离，前提是边界上的点少于“内部”，但它仍然昂贵，并且在最坏的情况下会失败。

试图搜索网络，但没有找到任何明智的答案-尽管这可能仅仅是我缺乏搜索技能。