我假设这些点是不同的，否则甚至可能不存在这样的线。
如果点是不同的，那么这样的线总是存在并且可以使用确定性的O(nlogn) 时间算法。
假设这些点是 P1、P2、...、P2n。假设它们并不都在同一条线上。如果是的话，那么我们就可以轻松地形成分割线。
首先平移点，使所有坐标（x 和 y）均为正值。
现在假设我们神奇地在 y 轴上有一个点 Q，使得这些点形成的线（即任何无限线 Pi-Pj）都不会穿过 Q。
现在，由于 Q 不在点的凸包内，我们可以很容易地看到，我们可以通过穿过 Q 的旋转线对点进行排序。对于某个旋转角度，一半的点将位于一侧，另一半点将位于一侧将位于这条旋转线的另一条上，或者换句话说，如果我们考虑按线 Pi-Q 的斜率排序的点，我们可以选择第（中位数）和（中位数+1）之间的斜率th 点。这种选择可以通过任何线性时间选择算法在 O(n) 时间内完成，而不需要实际对点进行排序。
现在选择点Q。
假设 Q 为 (0,b)。
假设 Q 与 P1 (x1,y1) 和 P2 (x2,y2) 共线。
然后我们就有了
(y1-b)/x1 = (y2-b)/x2（请注意，我们平移了这些点，使得 xi > 0）。
求解 b 给出
b = (x1y2 - y1x2)/(x1-x2)
（注意，如果x1 = x2，则P1和P2不能与Y轴上的点共线）。
考虑|b|。
|b| = |x1y2 - y1x2| / |x1 -x2|
现在让 xmax 为最右边点的 x 坐标，ymax 为最上面点的坐标。
还令 D 为两点之间的最小非零 x 坐标差（这是存在的，因为并非所有 xi 都相同，因为并非所有点都共线）。
然后我们就有了 |b|
因此，选择我们的点 Q (0,b) 使得 |b| > b_0 = xmax*ymax/D
D 可以在 O(nlogn) 时间内找到。
b_0 的大小可能变得非常大，我们可能必须处理精度问题。
当然，更好的选择是随机选A！以 1 的概率，您将找到所需的点，从而使预期运行时间为 O(n)。
如果我们能找到一种在 O(n) 时间内选取 Q 的方法（通过找到其他一些标准），那么我们就可以使该算法在 O(n) 时间内运行。
