【ABC181 C】「Collinearity」を解く【Python3】

無限に広い2次元平面上のN個の点の中から、相異なる3点を選んだ時に、それらが同一直線上にあるようなものが存在するかを判定する問題です。

提出

n = int(input())
xy = [list(map(int,input().split())) for _ in range(n)]

for i in range(n-1):
    li = []
    for j in range(i+1,n):
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        if x2==x1:
            slope = "0"
        else:
            slope = (y2-y1)/(x2-x1)
        if slope in li:
            print("Yes")
            exit()
        li.append(slope)

print("No")

入力はすべて整数です。

(x, y)はリストにしておきます。

3点[A, B, C]が同一線上にあるかどうかは、ABとACのそれぞれの傾きを計算して判断します。

プログラムでは、xy[i]とxy[j]の傾きを計算しています。

一度求めた傾きを重複して求める必要がないので、jの範囲は「i+1」からになります。

点xy[i]との傾きを、リスト「li」に入れていき、これまでのものと同じ傾きがあれば、「Yes」を出力してプログラムを終了させます。

iが増えるたびにリストをリセットする必要があります。

3点のxが等しい場合、もしくは、3点のyが等しい場合にも直線になるのですが、分母が0になってしまうのはまずいので、xが等しい場合は別で判定しています。