問題一覧 > 通常問題

No.2438 Double Least Square

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-5}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : abap34 / テスター : ebi_fly noya2 👑 potato167
お気に入りにしたユーザー ProblemId : 10003 / 自分の提出
問題文最終更新日: 2023-08-25 14:15:06
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
traP 作問ハッカソンコンテスト 001 (順位表) の他の問題:

Problem Statement

There are $N$ points on a two-dimensional coordinate plane. The coordinates of the $i$-th point are $(x_i, y_i)$.
For real numbers $a_1, a_2$, define
$f(x) = a_1 x + H$, which satisfies $f(0) = H$, and
$g(x) = a_2 x$, which satisfies $g(0) = 0$.
Find the minimum value of the following function $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\} $


In other words, find the minimum value of the sum of the $2$nd powers of the lengths of the arrows in the figure above.

Input

$N$
$H$
$x_1\ y_1$
$x_2\ y_2$
$x_3\ y_3$
$\vdots$
$x_N\ y_N$

  • All inputs are integers.
  • $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$

Output

Output the minimum value of $L$. Your answer is considered correct if its absolute or relative error from the expected solution is at most $10^{-5}$. The expected solution is guaranteed to have an absolute or relative error of at most $10^{-9}$ from the true value.

Sample

Sample 1
Input
4
10
4 1
4 3
4 7
4 9
Output
4

When $a_1 = -\dfrac{1}{2}, \ a_2 = \dfrac{1}{2}$, $L$ takes its minimum value $4$.

Sample 2
Input
1
2
1 1
Output
0
Sample 3
Input
9
58
5 48
51 24
35 41
49 29
52 2
43 10
6 31
11 53
35 33
Output
671.49094583682733627938

In this case, the minimum value of $L$ is $\dfrac{11669707521}{17378801} = 671.49094583 \dots$, and an answer is judged correct if its absolute or relative error from the expected solution $671.49094583682733627938$ is at most $10^{-5}$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。