Python 中计算落在同一直线上的点的数量的程序

假设我们有一个坐标列表，每个坐标由两个值 x 和 y 组成，表示笛卡尔平面上的一个点。现在找出落在某条直线上的点的最大数量。

因此，如果输入如下：coordinates = [[6, 2], [8, 3], [10, 4], [1, 1], [2, 2], [6, 6], [7, 7]]，则输出为 4，因为四个点 [1, 1]，[2, 2]，[6, 6]，和 [7, 7] 落在同一条直线上。

为了解决此问题，我们将按照以下步骤进行 −

• res ：= 0

• 对于 i 在点列表的范围从 0 到 size，执行以下操作

  • （x1，y1）：= 点[i]

  • slopes ：= 一个新地图

  • same ：= 1

  • 对于 j 在范围内的点从 i + 1 到点的大小，执行以下操作

    • （x2，y2）：= 点[j]

    • 如果 x2 与 x1 相同，则

    • slopes [inf] ：= 1 +（如果存在则为 slopes [inf]，否则为 0）

    • 否则当 x1 等于 x2 并且 y1 等于 y2 时，则

    • same ：= same + 1

    • 否则，

    • slope ：=（y2-y1）/（x2-x1）

    • slopes [斜率] ：= 1 +（如果存在则为 slopes [斜率]，否则为 0）

  • 如果 slopes 不为空，则

    • res ：= res 和 （same + 最大斜率列表的所有值）的列表的最大值
• 返回 res

示例

让我们看下面的实现，以更好地理解。

class Solution:
   def solve(self, points):
      res = 0
      for i in range(len(points)):
         x1, y1 = points[i][0], points[i][1]
         slopes = {}
         same = 1
         for j in range(i + 1, len(points)):
            x2, y2 = points[j][0], points[j][1]
            if x2 == x1:
               slopes[float("inf")] = slopes.get(float("inf"), 0) + 1
            elif x1 == x2 and y1 == y2:
               same += 1
            else:
               slope = (y2 - y1) / (x2 - x1)
               slopes[slope] = slopes.get(slope, 0) + 1
         if slopes:
            res = max(res, same + max(slopes.values()))
      return res
ob = Solution()
coordinates = [[6, 2], [8, 3], [10, 4], [1, 1], [2, 2], [6, 6], [7, 7]]
print(ob.solve(coordinates))

输入

[[6, 2], [8, 3], [10, 4], [1, 1], [2, 2], [6, 6], [7, 7]]

输出

4