Pythonで点のリストが同一直線上にあるかどうかを判定するプログラム

デカルト平面（XY座標平面）上の点のリストが与えられたとき、それらの点がすべて同一直線上に並んでいるかどうかを判定するプログラムを作成します。

例えば、入力が coordinates = [(5, 5), (8, 8), (9, 9)] の場合、これら3つの点は傾き1の直線上に並んでいるため、出力は True になります。

解法のアプローチ

すべての点が同一直線上にあるかどうかを確認するには、基準となる2点と他の各点との関係を調べます。具体的には、以下の手順で判定します。

• 最初の2点を基準点として取り出します：(x0, y0) と (x1, y1)
• 3番目以降の各点 (x, y) について、次の条件式をチェックします：
  (x0 − x1) × (y1 − y) ≠ (x1 − x) × (y0 − y1)
  この等式は「2つのベクトルの外積がゼロであること」、つまり3点が同一線上にあることを表します。この条件が成り立たない場合、その時点で False を返します。
• すべての点について条件が満たされれば True を返します。

なお、傾きを直接計算して比較する方法もありますが、分母がゼロになるケース（垂直な直線）での除算エラーを避けるため、外積を使った乗算による比較が安全で推奨されます。

実装例

以下にPythonでの実装例を示します。

class Solution:
    def solve(self, coordinates):
        (x0, y0), (x1, y1) = coordinates[0], coordinates[1]
        for i in range(2, len(coordinates)):
            x, y = coordinates[i]
            if (x0 - x1) * (y1 - y) != (x1 - x) * (y0 - y1):
                return False
        return True

ob = Solution()
coordinates = [[5, 5],[8, 8],[9, 9]]
print(ob.solve(coordinates))

入力

[[5, 5],[8, 8],[9, 9]]

出力

True

計算量について

このアルゴリズムは点のリストを一度だけ走査するため、時間計算量は O(n)、追加の記憶領域は O(1) で済みます。点の数が多くても効率的に動作します。