幾何は外積の符号から

点の位置関係を角度で求める代わりに、ベクトルの外積で左右を判定します。整数座標なら整数演算で扱えます。

言語：Python / 計算量：判定 O(1)

前提：制約から計算量を見積もる

考え方

1. A→B と A→C のベクトルを作ります。
2. 外積 ux*vy-uy*vx を計算。
3. 正なら反時計回り、負なら時計回り、0なら同一直線上。

具体例

A=(0,0),B=(2,0),C=(1,1)。外積は2×1-0×1=2なので、CはA→Bの左側です。

実装

def cross(a,b,c):
    ux,uy=b[0]-a[0],b[1]-a[1]
    vx,vy=c[0]-a[0],c[1]-a[1]
    return ux*vy-uy*vx
print(cross((0,0),(2,0),(1,1)))

注意する条件

外積0は同一直線を意味するだけで、線分上にあるとは限りません。座標の範囲判定も必要です。

確認問題

A=(0,0),B=(2,0),C=(1,1)の外積は？

実装課題

3点A,B,Cを各行 x y で入力。Cが有向直線A→Bの左なら Left、右なら Right、直線上なら On。A≠B、座標絶対値≤10^9。

入力:
0 0
2 0
1 1
出力:
Left

a=tuple(map(int,input().split()));b=tuple(map(int,input().split()));c=tuple(map(int,input().split()))
x=(b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0])
print("Left" if x>0 else "Right" if x<0 else "On")

読了の記録・下書き・メモへ