問題

xy平面上にN個の点が与えられる。最も多くの点を通るように直線を引いた時の点の最大値を求める問題

解法

HashMapを用いることでO(N²)で解くことができる。forループを２回使い２つの点を全列挙する。２つの点のを結ぶ傾きをキーとして、HashMapに保存する。バリューには１つの座標を固定した時に、傾きが同じ値になるものの出現回数を保存する。

少数値を比較するためには誤差を考慮する必要があるので、分数のまま扱うことにする。分母と分子をプロパティとして持つクラスを定義してあげる。分数を作る際に、約分できる時は約分をする。約分するためにユークリッドの互除法を用いて最大公約数を計算する

傾きを計算する時に、２つの点のｘ座標が等しいと分母が0となってしまい傾きがINFとなる。この時は、Lineクラスに傾きがINFか否かをチェックするためのプロパティを用意し場合分けに使う

入力値として与えられる点は、全く同じ座標のものも含まれる。よって同一座標の数をカウント(dup)することで対応する。