5

http://www.glassdoor.com/Interview/Google-Interview-RVW2382108.htm

我试图找到解决这个问题的方法。但我没有成功..任何人都可以给我一个关于如何处理这个问题的提示。

我将每人取 2 对两分。也就是说，我会制作2个和弦。找出它们的垂直平分线。使用这些平分线，我会找出圆的中心......

此外，我将提出圆的方程。并找到点 M 与圆的交点......那应该是最近的点。但是，该点可能存在也可能不存在于 N 个点的集合中

谢谢。

4

2 回答 2

5

假设圆的圆周上的点是“有序的”（即按围绕圆中心的角度排序），您可以使用基于角度的二分搜索，这应该可以实现O(log(n))边界。

  1. 计算A点M到圆心的角度 - O(1)。
  2. 使用二分查找I在圆周上找到最大角度小于A-的点O(log(n))。
  3. 由于圆是凸的，因此最接近的点M是I或I+1。计算两者的距离并取最小值 - O(1)。
于 2013-02-21T04:14:40.757 回答
2

为了找到最接近 M 的点，我们需要基于平面切割对点进行二元消除。需要对输入点进行一点预处理，之后我们可以在 O(lgn) 时间内找到最接近任何给定点 M 的点。

  1. 以 (r,θ) 格式计算（如果未给出）点的极坐标表示，其中 r 是与中心的距离，θ 是在 (-180,180] 范围内与 x 轴的角度。
  2. 将所有 N 个点按与 x 轴的角度递增的顺序排序。

请注意，最接近 M 的点的简单二进制搜索在这里不起作用，例如，

  • 如果给定点的排序使得 θ = (-130,-100,-90,-23,-15,0,2,14,170)，那么对于 θ = -170 的点 M，二分搜索将给出 -130 （40 度外）作为最近点，而 170（20 度外）是距离 M 最近的点。
  • 如果我们在排序时忽略符号（认为它会产生正确的输出），我们的新排序数组将看起来像 θ = (0,2,14,15,23,90,100,130,170)，对点 M 进行二分搜索，θ = - 6 将产生结果应该是 2 或 14 而在这种情况下 0 是最接近 M 的点。

要使用平面切割执行搜索操作，

  • 求通过圆心并垂直于连接圆心与点 M 的直线的平面切割线。
  • 根据平面 M 所在的一半，消除圆形平面的一半 [90+θ,-90+θ) 或 [-90+θ,90+θ)。
  • 使平面切割平行于第一个切割并通过前一个平面中间的点，并消除距离 M 较远的一半平面中的所有点，直到平面的近半部分没有任何点，在这种情况下消除飞机的近一半。
  • 继续切割平面，直到我们只剩下一点。该点是离 M 最近的点。整个操作需要 O(lgn) 步。

平面消除

如果数据是倾斜的并且没有均匀地分布在圆圈中，我们可以优化我们的平面切割，使每个切割都通过搜索操作中留下的那些点的中值（基于角度）。

于 2013-02-22T13:34:12.613 回答