同一直線上に並ぶ点のカウント

• 2次元平面上の $N$ 点の座標が与えられる
  • (1) 同一直線上に並んでいる3点組の個数を求めよ
  • (2) 最も多くの点を通る直線（複数ある場合はその一例）と、通る点の個数を求めよ

• 座標は整数値で与えられ、各点の座標 $|x|,|y| \le 10^9$
  • つまり、傾きを求める場合などに除算をおこない小数型にすると、精度が足りず、誤差が生じうる

全ての3点組について、同一直線上に存在するか調べればよい。

2点 $i,j$（$i \lt j$）を固定し、通る直線 $L$ を求める。
3点目を $j \lt k$ の範囲で探索し、$L$ 上にあった $k$ の個数+2が、その直線が通る点の個数。

全ての $i,j$ を通して、最も通った点の数が多い直線が求めるもの。

いくつかの方法がある。なるべく途中で小数が出てこないようにする方がよい。

3点に囲まれた三角形の面積は以下で求められる。

• $\dfrac{1}{2}|(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)|$

これが0なら同一直線上にある。

幾何でよく使われるユーティリティ関数に、ccw（Counter-ClockWise、反時計回り判定）がある。
$A→B$ の線分から見て、$B→C$ がどっち向きに曲がっているか（まっすぐか）を、外積で判定する。

• ２．計算幾何のインフラ整備　　　シリーズ：「基礎的計算幾何ライブラリの作り方」 - Senの競技プログラミング備忘録

汎用性があるので、これで判定してもよい。

2点組ごとに「2点を結ぶ直線の方程式 $ax+by+c=0$ の係数 $(a,b,c)$」を求め、それごとにカウントする。

$(x_1,y_1),(x_2,y_2)$ を通る直線の方程式は、$d_x=x_2-x_1,d_y=y_2-y_1$ として、以下のようになる。

• $d_yx - d_xy + (d_xy_1 - d_yx_1)=0$
• 二点を通る直線の方程式の３タイプ | 高校数学の美しい物語

ただし、係数に定数倍をかけたものは $(a,b,c)$ が異なっても同一の直線を示すので、それらを統一する必要がある。

• $d_x$ と $d_y$ は、GCDで割って互いに素にしておく
• $d_x$ が負の場合、$d_x,d_y$ に $-1$ をかける
• $d_x$ が0かつ $d_y$ が負の場合、$d_y$ を正にする

こうすると、違いを吸収して、同一の直線は同一の $(a,b,c)$ となる。

$k$ 個の点が並ぶ直線は、$\dfrac{k(k-1)}{2}$ 回カウントされることになるので、 最終カウント結果から、各直線にいくつの点が並ぶか復元できる。

$O(N^2)$ 本の全てのカウントされた直線に対して個数を復元する。$k$ 個の点が並ぶ直線上には、${}_kC_{3}$ 組の3つ組みがある。

最も多くカウントされた直線が、求める直線である。