确定是否有一条所有点都在上面的线。

Question

我试图创建一个算法来确定平面上是否有一条水平的或垂直的线，这样对于这个地方上的每一点，它要么是在垂直线上，要么是在水平线上，或者是两条线上。该算法只需序贯，并返回真或假。

我知道需要做什么，即我需要检查每个点的位置，但我不知道如何检查它是否在一条线上。有什么想法吗？

提前谢谢！！

Answer 1

用x坐标和y坐标对所有的点进行排序。如果每个点都是在一条水平线上或者在一条垂直线上，那么这些线中至少有一条必须覆盖至少一半的点，而像这样的水平线不能超过两条，或者像这样的两条以上的垂直线，因为你不能有两条以上的水平线，每条水平线上有一半的点。

所以，通过x坐标排序，在同一个x坐标上寻找很多点，你最多有两条垂直线的候选点，最多两条水平线的候选点按y坐标排序。对于每一条(最多四条)候选线，查看所有不适合于这条线的点，并查看它们的y-坐标(或x-坐标)，看看它们是否都适合于另一种类型的直线。如果他们这么做你就完蛋了。如果没有，最多可以尝试其他三种可能性。

Answer 2

您按顺序遍历每个点并比较它们的坐标，知道它们必须共享相同的x组件(横坐标)、y组件(纵坐标)，或者两者都共享。您的目标是确定这些值，然后检查所有的点是否至少有一个。

• 第一点可能有一个或两个正确，所以您将这两个组件保持为潜在的正确值，
• 第二个点应该至少有一个与第一个相同，所以您将公共组件标记为水平( x)或垂直线( y)的正确组件。
• 在下一个点上循环，直到所有的点都共享相同的组件，在前两个点之间，如果发现一个点不在这条线上，那么它必须属于另一个点，所以您已经发现了第二个正确的组件，
• 现在你检查所有剩余的点l，如果其中一个没有任何一个成分，结果是假的。