Pythonで同一直線上にある点の最大数を求めるプログラム

問題の概要

座標のリストが与えられているとします。各座標は x と y の2つの値から構成され、デカルト平面(直交座標系)上の1点を表しています。ここで求めたいのは、「ある1本の直線上に同時に乗っている点の最大数」です。

たとえば、入力が [[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]] の場合、出力は 4 になります。これは [1, 1]・[2, 2]・[6, 6]・[7, 7] の4点が、直線 y = x 上にきれいに並んでいるためです。

考え方：傾きごとに点をグループ化する

この問題は「傾き」に着目すると効率よく解けます。ある基準点 P から見て傾きが等しい点は、必ず P を通る同一直線上に存在するという幾何学の基本性質を利用します。各点を順番に基準点とし、他の点までの傾きを計算して、同じ傾きの点がいくつあるかを辞書(ハッシュマップ)で数えていきます。

アルゴリズムの手順

1. 答えを格納する変数 res を 0 で初期化します。
2. 各点 i を基準点としてループします。
   • (x1, y1) に points[i] の座標を設定します。
   • 傾きを記録するための空の辞書 slopes を用意します。
   • same を 1 に初期化します(基準点自身をカウント)。
   • j を i + 1 以降のすべての点についてループします。
     • (x2, y2) に points[j] の座標を設定します。
     • x1 == x2 かつ y1 == y2 の場合(完全に重複した点)→ same を +1 します。
     • x2 == x1 の場合(縦の直線 = 傾きは無限大)→ slopes[inf] を +1 します。
     • それ以外の場合 → 傾き (y2 − y1) / (x2 − x1) を計算し、対応するキーのカウントを +1 します。
   • slopes が空でなければ、res を max(res, same + slopes の最大値) で更新します。
3. 最終的な res を返します。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

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 x1 == x2 and y1 == y2:
               same += 1
            elif x2 == x1:
               slopes[float("inf")] = slopes.get(float("inf"), 0) + 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

処理のポイントと計算量

• 時間計算量: 全ペアについて傾きを調べるため、O(n²) となります。
• 空間計算量: 各基準点ごとに傾きの辞書を保持するため、最大 O(n) です。
• 重複点の扱い: 同じ座標が複数回現れるケースでは、重複判定を先に行うことで、縦の直線(傾き無限大)との誤分類を防げます。
• 精度への注意: 傾きを float で扱うと丸め誤差により、本来同一直線上の点が別グループに分かれる可能性があります。厳密さが必要な場合は、fractions.Fraction を使うか、分子・分母を gcd で約分した既約分数をキーにするのが安全です。

まとめ

「同一直線上の最大点数」問題は、基準点ごとに傾きを集計するシンプルな発想で解決できます。O(n²) の二重ループでも十分実用的であり、傾きの計算方法と辞書によるカウントの組み合わせを理解しておくことが、類似の幾何学問題を解く上での強力な武器になります。