http://www.glassdoor.com/Interview/Google-Interview-RVW2382108.htm
我已经尝试解决这个问题,但一直没有成功。请问有人可以给我提示如何继续解决这个问题。我将使用两个点对的2条弦,即2个弦。找到它们的垂直平分线。使用这些平分线,我将找到圆的中心...
此外,我将提出圆的方程,并找到点M与圆的交点...那应该是最接近的点。然而,该点可能存在于N个点的集合中,也可能不存在。
谢谢。
http://www.glassdoor.com/Interview/Google-Interview-RVW2382108.htm
我已经尝试解决这个问题,但一直没有成功。请问有人可以给我提示如何继续解决这个问题。O(log(n))
的限制。
M
到圆心计算角度 A
- O(1)
。A
的点 I
- O(log(n))
。M
的点是 I
或 I+1
。分别计算到两个点的距离,并取最小值 - O(1)
。O(nlog(n))
)。我假设点是按顺序给出的。由于这是一个面试问题,我认为你可能会在当时与他们讨论这些想法... - Darren Engwirda