ABC 401-500/ABC422E - Colinear - 競技プログラミング用 知識集積所

---

問題

ABC422E

必要知識

B以下レベルの内容は省略

• 特になし

考え方

3m個の点のうち、k個（m<k<2*m）の点が同一直線状にあったとする。
これらの点を3個ずつmグループにわけて、各グループ内でそのうち2点を通る直線を全て求める。
こうして3m本の直線ができるが、この中には求めたい直線が繰り返し出てくるはずである。

同一直線状の点が……

• 3個のグループと0個のグループがあったら、2個と1個に変える
• 3個のグループと1個のグループがあったら、2個と2個に変える
• 2個のグループと0個のグループがあったら、1個と1個に変える

と、その直線が出てくる回数が減る。
つまり、k-m個の2個グループと、2m-k個の1個グループを作るのが出現回数最小で、それでもk-m回は出現する。
もちろん、kが2*m以上の場合はもっと多い。

ということで、以下の手順を踏む。
与えられた点を3個ずつグループにわける（足りない分は、適当に点を付け足す）。
すると、n/3（切り上げ）個のグループになる。
それぞれの中で2点ずつのペアを3組作り、その2点を通る直線の式を求めて、何が何回出てきたかmap※等でカウントする。
与えられた点の中には少なくとも(n+1)/2個の直線上の点があるはず。
ということは、条件を満たす直線は、求めた直線群の中にn/3（切り上げ）-(n+1)/2回以上現れる。
これはnがある程度大きい場合はおよそn/6であるので、候補は最大でも6本。
つまり、これらの候補を1つ1つ調べても、十分間に合う。

解答例

解答例

注意点

直線の式の表記の自由度に注意

ax+by+c=0という式は、a,b,cを全て定数倍しても同じ直線を表す。
したがって、カウント時に注意しなければならない。
すなわち、(x1,y1),(x2,y2)を通る直線は、

a = y1 - y2
b = x2 - x1
c = x1*y2 - x2*y1

とするだけでは不十分で、

• a,b,cが互いに素でない場合は、最大公約数で割る
• 符号違いを除去する（a<0ならa>0に、a==0かつb<0ならb>0に、など）

をして、同一直線が必ず同一式になるように規格化しなければならない。

別解