P13210 [GCJ 2016 Finals] Radioactive Islands

You are steering a boat from the coordinates $(-10, A)$ to the coordinates $(10, B)$. The coordinates are measured in kilometers, and your boat travels at a constant speed of 1 kilometer per hour. You have full control over the path the boat takes. We model the boat as a single point. There are $\mathbf{N}$ islands in the area; we model them as single points. The i-th island is at the coordinates ($0$, $\mathbf{C}_{\mathbf{i}}$). The area is radioactive, and you constantly receive 1 microsievert per hour of radiation from the general environment, no matter where you are. Moreover, the islands themselves are radioactive, and you constantly receive additional radiation at a rate of $(\mathbf{D}_{\mathbf{i}})^{-2}$ microsieverts per hour from the i-th island, where $\mathbf{D}_{\mathbf{i}}$ is your current distance (in kilometers) from the i-th island. (Formally: let $\mathbf{D}_{\mathbf{i}}(\mathbf{t})$ be your distance from the i-th island as a function of time $\mathbf{t}$, and $\mathbf{X}$ be the total time your journey takes. Then the total radiation received from the i-th island is the definite integral from $0$ to $\mathbf{X}$ of $\mathbf{D}_{\mathbf{i}}(\mathbf{t})^{-2}$.) You can get as close to an island as you would like, as long as you do not match its exact coordinates. Find the minimum total radiation dose that you can receive if you plot your course optimally.

The first line of the input gives the number of test cases, $\mathbf{T}$; $\mathbf{T}$ test cases follow. Each test cases consists of two lines. The first line of a test case consists of three values: an integer $\mathbf{N}$, and two floating-point numbers $\mathbf{A}$ and $\mathbf{B}$, as described in the statement above. The second line of a test case consists of $\mathbf{N}$ floating-point numbers $\mathbf{C}_{\mathbf{i}}$; the i-th of these numbers gives the y coordinate of the i-th island. All floating-point numbers are specified to exactly two decimal places.

For each test case, output one line containing `Case #x: y`, where $\mathbf{x}$ is the test case number (starting from 1) and $\mathbf{y}$ is the minimum radiation dose (in microsieverts) received while completing the journey. $\mathbf{y}$ will be considered correct if it is within an absolute or relative error of $10^{-3}$ of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

**Sample Explantion** Here is a diagram of the optimal path for sample case #1. We have enlarged the island to make it more visible, but remember to treat it as a single point.  **Limits** - $-10.00 \leq \mathbf{A} \leq 10.00$. - $-10.00 \leq \mathbf{B} \leq 10.00$. - $-10.00 \leq \mathbf{C}_{\mathbf{i}} \leq 10.00$, for all $\mathbf{i}$. - $\mathbf{C}_{\mathbf{i}} \neq \mathbf{C}_{\mathbf{j}}$, for all $\mathbf{i} \neq \mathbf{j}$. **Small dataset (25 Pts, Test Set 1 - Visible)** - Time limit: ~~120~~ 30 seconds. - $\mathbf{T} \leq 20$; - $\mathbf{N} = 1$. **Large dataset (25 Pts, Test Set 2 - Hidden)** - Time limit: ~~240~~ 60 seconds. - $\mathbf{T} \leq 50$; - $1 \leq \mathbf{N} \leq 2$.