同一直線上に並ぶ点のカウント
問題設定
- 2次元平面上の N 点の座標が与えられる
- (1) 同一直線上に並んでいる3点組の個数を求めよ
- (2) 最も多くの点を通る直線(複数ある場合はその一例)と、通る点の個数を求めよ
制約とか
- 座標は整数値で与えられ、各点の座標 |x|,|y|≤109
- つまり、傾きを求める場合などに除算をおこない小数型にすると、精度が足りず、誤差が生じうる
解法例
O(N3) 解法
(1)
全ての3点組について、同一直線上に存在するか調べればよい。
(2)
2点 i,j(i<j)を固定し、通る直線 L を求める。
3点目を j<k の範囲で探索し、L 上にあった k の個数+2が、その直線が通る点の個数。
全ての i,j を通して、最も通った点の数が多い直線が求めるもの。
3点が同一直線上か調べる方法
いくつかの方法がある。なるべく途中で小数が出てこないようにする方がよい。
面積が0
3点に囲まれた三角形の面積は以下で求められる。
- 12|(x2−x1)(y3−y1)−(x3−x1)(y2−y1)|
これが0なら同一直線上にある。
反時計回り判定
幾何でよく使われるユーティリティ関数に、ccw(Counter-ClockWise、反時計回り判定)がある。
A→B の線分から見て、B→C がどっち向きに曲がっているか(まっすぐか)を、外積で判定する。
汎用性があるので、これで判定してもよい。
O(N2) 解法
2点組ごとに「2点を結ぶ直線の方程式 ax+by+c=0 の係数 (a,b,c)」を求め、それごとにカウントする。
(x1,y1),(x2,y2) を通る直線の方程式は、dx=x2−x1,dy=y2−y1 として、以下のようになる。
- dyx−dxy+(dxy1−dyx1)=0
ただし、係数に定数倍をかけたものは (a,b,c) が異なっても同一の直線を示すので、それらを統一する必要がある。
- dx と dy は、GCDで割って互いに素にしておく
- dx が負の場合、dx,dy に −1 をかける
- dx が0かつ dy が負の場合、dy を正にする
こうすると、違いを吸収して、同一の直線は同一の (a,b,c) となる。
k 個の点が並ぶ直線は、k(k−1)2 回カウントされることになるので、 最終カウント結果から、各直線にいくつの点が並ぶか復元できる。
(1)
O(N2) 本の全てのカウントされた直線に対して個数を復元する。k 個の点が並ぶ直線上には、kC3 組の3つ組みがある。
(2)
最も多くカウントされた直線が、求める直線である。