将点平面分成两个相等的两半

给定一个二维平面，其中有n个点。我需要生成将平面划分为一条直线的方程，以便一侧有n / 2个点，另一侧有n / 2个点。

我假设这些点是截然不同的，否则可能根本没有这样一条线。

如果点是不同的，则这样的线将始终存在，并且可以使用 确定性 O（nlogn）时间算法找到。

说点是P1，P2，…，P2n。假设它们不在同一行。如果是这样，那么我们可以轻松地形成分割线。

首先平移点，以使所有坐标（x和y）均为正。

现在假设我们神奇地在y轴上有一个点Q，以使由这些点形成的线（即任何无限线Pi-Pj）都不会穿过Q。

现在，由于Q不在点的凸包内，我们可以很容易地看到，可以通过穿过Q的旋转线对点进行排序。对于某个旋转角度，一半的点将位于一侧，而另一半将位于该旋转线的另一条线上，或者换句话说，如果我们考虑按点Pi-

Q的斜率排序的点，则可以选择第（median）和（median +

1）之间的斜率点。可以通过任何线性时间选择算法在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坐标差（存在，因为并非所有x都是相同的，因为并非所有点都是共线的）。

然后有| b | <= xmax * ymax / D。

因此，选择我们的点Q（0，b）为| b | > b_0 = xmax * ymax / D

D可以在O（nlogn）时间找到。

b_0的大小可能会变得很大，我们可能不得不处理精度问题。

当然，更好的选择是随机选择Q！以概率1，您将找到所需的点，从而得出预期的运行时间O（n）。

如果我们可以找到在O（n）时间中选择Q的方法（通过找到其他标准），则可以使该算法在O（n）时间中运行。