Pythonの行にあるポイントの数を数えるプログラム

座標のリストがあるとします。各座標には、デカルト平面上の点を表す2つの値xとyがあります。次に、ある線上にあるポイントの最大数を見つけます。

したがって、入力が座標のようなものである場合=[[6、2]、[8、3]、[10、4]、[1、1]、[2、2]、[6、6]、[7、7 ]]の場合、ポイントは[1、1]、[2、2]、[6、6]、[7、7]]であり、線上にあるため、出力は4になります。

これを解決するには、次の手順に従います-

• res：=0

• 0からポイントリストのサイズまでの範囲のiについては、実行してください

  • （x1、y1）：=points [i]

  • 傾斜：=新しい地図

  • 同じ：=1

  • i + 1からポイントのサイズまでの範囲のjについては、次のようにします

    • （x2、y2）：=points [j]

    • x2がx1と同じ場合、

      • 勾配[inf]：=1 +（終了する場合は勾配[inf]、それ以外の場合は0）

    • それ以外の場合、x1がx2と同じで、y1がy2と同じである場合、

      • 同じ：=同じ+ 1

    • それ以外の場合

      • 勾配：=（y2-y1）/（x2-x1）

      • 勾配[勾配]：=1 +（終了する場合は勾配[勾配]、それ以外の場合は0）

  • スロープが空でない場合は、

    • res：=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