平均誤差
(paizaランク S 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
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
・ 1 行目には、点の数 n と選ぶ点の数 m が半角スペース区切りで与えられます。
・ 続く n 行には、各点の座標 x_i, y_i が半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
傾き 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
・ 入力はすべて整数
- 入力例1
-
5 3
1 2
2 1
2 2
2 3
3 2
- 出力例1
-
7 5
