問題一覧 > 通常問題

No.2438 Double Least Square

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-5}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 12
作問者 : abap34abap34 / テスター : ebi_flyebi_fly noya2noya2 👑 potato167potato167
9 ProblemId : 10003 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-25 14:15:06

問題文

二次元座標上に $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もしくは右上の雲マークをクリックしてアカウントを作成してください。