这是我以前在一次工作面试中被问到的问题，但我仍然无法想出一个明智的答案。
问题是：
给你一组点(x,y)，找出其中距离最远的两个点。它们之间的距离要求最大。
例如，对于这些点：(0,0), (1,1), (-8,5) - 距离最远的是：(1,1) 和 (-8,5)，因为它们之间的距离比 (0,0)-(1,1) 和 (0,0)-(-8,5) 都要大。
显而易见的解决方法是计算所有点之间的距离并找到最大值。但是这种方法的时间复杂度是O(n^2)，对于大型数据集来说代价太高了。
还有一种方法是首先跟踪位于边界上的点，然后计算它们之间的距离，这基于边界上的点数量应该比“内部”少的前提下，但是这种方法仍然很耗时，并且在最坏情况下可能会失败。
我尝试过搜索网络，但没有找到任何合理的答案 - 尽管这可能只是我的搜索技巧不足所致。
给定点集 {(x1,y1), (x2,y2) ... (xn,yn)}，找出其中最远的两个点。
我的方法：
1). 首先需要一个参考点 (xa,ya), 它可以通过以下公式计算得到：
xa = ( x1 + x2 +...+ xn )/n
ya = ( y1 + y2 +...+ yn )/n
2). 计算点 (xa,ya) 到每个点 (x1,y1), (x2,y2),...(xn,yn) 的距离
其中距离最远的点就是要求的“最远点”(xb,yb)。
3). 计算点 (xb,yb) 到每个点 (x1,y1), (x2,y2),...(xn,yn) 的距离
其中距离最远的点就是另一个“最远点”(xc,yc)。
这样就可以在 O(n) 的时间复杂度内找到最远的两个点 (xb,yb) 和 (xc,yc)。
例如，对于点：(0,0)，(1,1)，(-8,5)