以下是来自 careercup.com 的 Google 面试部分的问题：
给定 2*n + 3 个点在 2d 空间中，没有 3 个点共线且没有 4 个点位于一个圆上，
设计一个算法，该算法将找到一个包含 n 个点在其内、n 个在其外并在其上包含 3 个点的圆。
我可以想到一个 O(n^4) 解决方案：
a) 选择任何 3 个点 [以 C(2n+3,3) 方式] 并用这些 (O(n^3))
b) 现在每个圆，检查是否正好有 'n' 个点在里面 O(n)
由于这是一种幼稚的方法，我想问是否有更好的方法
来解决这个问题？即 O(n log n) 的顺序
这是一个 O(n) 的解决方案。
令 S 为点集。令 p 为 S 的最左边点。然后 p 在 S 的凸包上。令 q 为 S 的点，最小化从 p 向左的射线与从 p 开始并通过 q 的射线之间的角度。p 和 q 都可以在 O(n) 时间内找到。线段 pq 是 S 的凸包的一条边，并且 S 的任何点都不位于线 pq 的左侧。
取线段 pq 的轴 A。包含 p 和 q 的圆的中心正好是轴 A 上的点。对于 A 上的每个点 c，令 C(c;p,q) 是以 c 为圆心并包含 p 和 q 的圆。如果 c 是 A 的左侧足够远的点，则 C(c;p,q) 在内部没有 S 的点。如果 c 是 A 的一点向右足够远，则 C(c;p,q) 具有 S 的除 p,q 之外的所有点（p 和 q 在圆上）。如果我们将 c 从左向右移动，S 的点将一个一个地进入圆 C(c;p,q) 并且永远不会离开。所以在两者之间的某个地方，A 上有一个点 c，使得 C(c;p,q) 包含 p,q 和 S 的另一个点，并且内部正好有 n 个其他点。
这可以在 O(n logn) 中清楚地找到：对于 S 的除 p 和 q 之外的每个点 s，找到 A 上的点 c，使得 C(c;p,q) 包含 p,q 和 s。点 c 是轴 A 和线段 qs 的轴的交点。请注意，当我们在沿 A 移动时经过 c 时，s 进入了圆 C(c;p,q)。通过增加 x 坐标对这些中心进行排序并取 (n+1)-st，因为这是 S 的 n 个点已经在 C(c;p,q) 内并且 p、q 和另外一个点在上的点C(c;p,q)。要在 O(n) 中执行此操作，您会找到 (n+1)-st 而无需将它们全部排序。
另一种 O(n) 算法，但更简单。
而这三点就是答案。
如：
又因为角 C < 角 A，所以点 C 在圆外（由 A 和 x, y 组成）。
角度 B > 角度 A，所以点 B 在圆内
At the ideal condition, when the circle has n points outside, n inside and 3 on it, The distance from the center of exactly n points will be more than the radius, and exactly n points less than the radius.. and only 3 points equal to the radius.. This will help you see how many are outside/inside quickly at a particular instant..
Make a vornoi diagram on the 2D points, this helps in finding which point is near to which other points.. Search on it if you need to know the concept.
Start by making a circle from any 3 adjacent points..
store the distance of all points to the center of this circle in an array.. points with distance more than R are outside and distance less are inside.
Progressively, leave a point on the circle and choose a point nearest to the boundary of the circle but outside the circle, to make a new circle.. and recalculate the array.
If we call the count of points inside as Nin and count of outside as Nout.. Nout will start decreasing and Nin will start increasing slowly. Keep doing this till they become equal( ur done, if so) or Nin exceeds Nout.. If this happens, make a new circle by choosing a point inside and near the boundary. Keep doing this until you get Nin == Nout at which point you have the solution..
Note that, taking the new point outside the circle, would increase the circle radius, and taking the new point inside the circle decreases the radius.
This is the first decent solution that came to my mind. This may need improving on certain aspects. I would expect the complexity to be much better than a brute force solution. I leave the calculation to you. :)
您可以考虑使用QuadTree : Quadtree on wiki 然后使用此结构您可以扫描每个节点的接近度。似乎有一个名为Query Range的函数。此功能将使您比我认为的详尽地挑选圆圈更精确。
请注意，这不是解决方案，只是让您入门的一个想法。
在 O(n) 时间内解决此问题的一种简单方法是在循环中使用反转。
概要
r从集合中选择任何点 O(x,y) 作为原点，然后选择一个以您选择的点为中心的半径圆。如果所有点都平移了一个量（-x，-y），那么计算将被简化，这样点 O 就成为原点。
一旦你选择了一个原点和一个圆，就你选择的圆对集合中的所有其他点执行反演操作。在坐标中，我们将点 P(x,y) 映射到坐标为 的新点 P' (x',y') = (x,y)*r^2/(x^2+y^2)。原点 O(0,0) 到达无穷远点。
通过反演变换，问题简化为找到一条具有所需属性的线（通过两个变换点，因为一条线总是通过无穷远的点；此外，该线应该将剩余的变换点分成两个相等的集合）。
请注意，反演将 3 个共线和 4 个同心点的集合映射到 3 个共线和 4 个同心点的集合上，因此在变换后的集合中我们没有 3 个共线点和 4 个同心点。
为了构造圆，我们然后执行逆反转（这与原始反转相同，因为圆中的反转是对合，自逆变换）。这会将线拉回穿过第一个选定点和原始集合中的另外两个点的圆。剩下的一半在圆圈内，一半在圆圈外。
线的对应问题
现在我们将问题简化为：给定平面上的 2n+2 个点，找到一条通过其中 2 个点的线，使得剩下的 2n 个点中，n 位于线的一侧，n 位于线的另一侧.
我们可以在 O(n) 时间内回答这个问题，如下所示。首先，我们需要集合的凸包边界中的一个点（我们不需要整个凸包）。我们可以通过在集合中找到坐标最小 x 值的点来找到这样的点 P，这可以使用 Quickselect 算法在 O(n) 时间内完成。
现在我们知道我们所有的点都在 P 右侧的半空间中。下一步的想法是找到所有点相对于水平线 h 到 P 的中角的点 Q。同样，可以使用快速选择算法在 O(n) 时间内完成。不可能有两个角度相同的点，因为不可能有三个点共线。
线 PQ 穿过其中两个点，并根据角度 RPh 大于 QPh 还是小于 QPh（负角度在 h 以下）将剩余的点 R 分成两等份。
可能会出现一个小问题：如果线通过原点，则反转会将其带到另一条线，而不是圆。然而，这种情况不会出现，因为这意味着我们在原始集合中有 3 个共线点，问题陈述保证不会出现这种情况。