从一组坐标中确定将形成一条线的点

Question

我想编写一个程序，在笛卡尔平面上生成 10 - 100 个随机坐标，并且它应该找到哪些点将形成一条线。

它应该是至少四个可以形成一条线的点的组合。为此，我可以找到四个选定点之间的斜率，以确定它们是否可以形成一条线。

然而，困难的部分是如何将所有点组合起来？我想使用蛮力方法，找到至少四个点的所有组合，然后检查它们之间的斜率，看看它们是否可以形成一条线。

关于如何解决这个问题的任何建议（例如有效地找到组合）将不胜感激。

Answer 1

我认为尝试所有 4 点组没有任何好处。只需取每对点，计算它们形成的直线的方程 y = mx + c，并将每对 (m, c) 插入到一个数组中。然后对这个数组进行排序（无论 m 还是 c 是第一个排序键）。属于同一行的所有点对将在排序数组中显示为连续块：如果同一行上有 n 个点，则相应块中将有 n^2 个连续元素，但很容易识别 n 个连续元素不同的点。时间和空间复杂度：O(n^2 log n)。