問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
paiza 君は、2 次元平面上にある n 個の点から m 個の点を選び、できるだけ傾きが大きい近似曲線 y = ax を求めようとしています。
近似曲線は、以下のようにして求めます。
1. m 個の各点の座標 x_i, y_i について、直線との符号付き距離を d_i = y_i - a * x_i とする。
2. d_i の平均値に対して絶対値を取ったものを最小にするように a を選ぶ。(絶対値の平均ではないので注意)
上の方法で計算する近似曲線は、選ぶ点を決めたときに一意に定まることが証明できます。
選ぶ点を自由に決めることができるとき、近似曲線の傾き a の最大値を求めてください。
n m
x_1 y_1
x_2 y_2
...
x_n y_n
傾き a の最大値 x を求め、x = b/c を満たす正整数 b, c を、この順に半角スペース区切りで出力してください。
ただし、出力される b, c の組は、x = b/c を満たす正整数 b, c のうち、c が最小となる組である必要があります。
また、末尾に改行を入れ、余計な文字を含んではいけません。
・ 1 ≦ m ≦ n ≦ 1000 = 10^3
・ 1 ≦ x_i, y_i ≦ 1000 = 10^3
・ 入力はすべて整数
5 3
1 2
2 1
2 2
2 3
3 2
7 5