No.2438 Double Least Square
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
abap34
noya2