部外者をはじけ Scala編（paizaランク B 相当）

あなたはテレビ局の制作スタッフです。
あなたは今ヘリで上空から撮影したとあるイベントの映像を編集しています。
このイベントは参加者が一直線に一本の長い列を作ることで有名です。
あなたはこれを強調するため、映像の列上に赤い直線を引こうとしていますが、1 コマごとに手動で線を引くのが面倒になりました。

実はプログラマーでもあるあなたは、この作業をプログラムで自動化することにしました。
映像から人の座標を検出するプログラムは既にできていますが、いざ直線を引く段階で人の列と引いた直線がずれるバグが発生しました。
どうやら人の座標検出の際に、イベント参加者以外の部外者の座標を同時に検出してしまっていることが原因のようです。

部外者を検出し、バグを取り除くのが今回のミッションです。
ここでは直線から 2 m以上離れた人を部外者として処理することにします。
ある直線を引いた際に最も部外者が少なくなるような直線を、列に対する「正しい直線」とします。



各人物には 1 から N までの番号が振られます。
映像に映った各人物の座標が与えられるので、正しい直線を引いたときの部外者を検出するプログラムを作成しましょう。

人の大きさは考えず、点としてみなしてよいものとします。
また、正しい直線上にいる人物が最低二人以上存在することは保障されています。
また、条件をみたす直線は複数存在する場合がありますが、答えは必ず一意に定まります。

ここで、任意の二点 (x_1, y_1), (x_2, y_2) を結ぶ直線の方程式 ax - by + c = 0 は次のように計算できます。

(y_2-y_1) * x - (x_2-x_1) * y + {(x_2-x_1) * y_1 - (y_2-y_1) * x_1} = 0

また、ある点 (x_i, y_i) と直線 ax + by + c = 0 との距離 d_i は次のように求まります。

d_i = |a * x_i + b * y_i + c| / (a^2 + b^2)^(1/2)