No.2438 Double Least Square
タグ : / 解いたユーザー数 12
作問者 : abap34 / テスター : ebi_fly noya2 👑 potato167
問題文
二次元座標上に $N$ 個の点があります。$i$ 番目の点の座標は $(x_i, y_i)$ です。
実数 $a_1, a_2$ に対して、
$f(0) = H$ を満たす $f(x) = a_1 x + H$,
$g(0) = 0$ を満たす $g(x) = a_2 x$ を定めます。
次の関数 $L(a_1, a_2)$ の最小値を求めてください。
$
L(a_1, a_2) = \displaystyle \sum_{i=1}^N \ \min \left\{ \left( y_i - f(x_i) \right)^2, \left( y_i - g(x_i) \right)^2 \right\}
$
つまり、上図の矢印の長さの $2$ 乗の総和の最小値を求めてください。
入力
$N$ $H$ $x_1\ y_1$ $x_2\ y_2$ $x_3\ y_3$ $\vdots$ $x_N\ y_N$
- 入力は全て整数
- $1 \leq N \leq 2 \times 10^3$
- $1 \leq H \leq 5 \times 10^2$
- $1 \leq x_i \leq 5 \times 10^2$
- $1 \leq y_i \leq 5 \times 10^2$
出力
$L$ の最小値を出力してください。 想定解との絶対誤差または相対誤差が $10^{-5}$ 以下であれば正解として扱われます。 想定解は真の値との絶対誤差または相対誤差が $10^{-9}$ 以下であることが保証されています。
サンプル
サンプル1
入力
4 10 4 1 4 3 4 7 4 9
出力
4
$a_1 = -\dfrac{1}{2}, \ a_2 = \dfrac{1}{2}$ のとき、$L$ が最小値 $4$ をとります。
サンプル2
入力
1 2 1 1
出力
0
サンプル3
入力
9 58 5 48 51 24 35 41 49 29 52 2 43 10 6 31 11 53 35 33
出力
671.49094583682733627938
このケースでは、 $L$ の最小値は $\dfrac{11669707521}{17378801} = 671.49094583 \dots$ になり、 想定解 $671.49094583682733627938$ との絶対誤差または相対誤差が $10^{-5}$ 以下であれば正解となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。