競プロで2つの格子点を通る直線を一意に表したい

競プロをやってると、2つの格子点(a, b), (c, d)を通る直線を考えたいことがよくあります。

そのときに、複数の直線集合の中から同一の直線をグルーピングしたい場合というのもよくあります。

そういうときに、同じ直線は同じ表現になり、異なる直線は異なる表現になるような表現があると便利です。

そういう方法を紹介します。

簡単です。直線を、次のような形で表します。

よくある直線の表現ですが、gcd(a, b) = 1という条件が加わっています。

この条件を加えることで、全ての(2つの格子点を通る)直線は一意に表すことができます。 (証明は省略します)

格子点(p, q), (r, s)を通る直線の表現を計算してみましょう。

まず、dx = r - p, dy = s - q とおくと、a = -dy, b = dx です。

すると、c = -a - b となります。

よって、(a, b, c) = (-dy, dx, -a - b) と求まりました。

(a, b, c)の値は直線によって一意なので、(a, b, c)をtupleにしてmapなどで持つと、いい感じに同一な直線のグルーピングができます。

法線を求める問題ですが、考え方は同じです。