방사능 섬 (Small)

배가 (-10, A)에서 (10, B)까지 시속 1km로 이동할 때, 기본 1마이크로시버트와 각 섬 (0, C_i)에서의 1/D^2 방사선을 합한 최소 선량을 구한다.

어려움8기하수학그리디구현아직 제출이 없습니다시간 제한30초메모리 제한512 MB

문제

배를 몰아 좌표 (10,A)(-10, A)에서 좌표 (10,B)(10, B)까지 가려고 한다. 좌표의 단위는 킬로미터이고, 배는 시속 1킬로미터의 일정한 속력으로 움직인다. 배가 지나갈 경로는 마음대로 정할 수 있다. 배는 하나의 점으로 생각한다.

이 해역에는 섬이 NN개 있고, 각 섬도 하나의 점으로 생각한다. ii번째 섬은 좌표 (0,Ci)(0, C_i)에 있다.

해역 전체가 방사능에 오염되어 있어서, 어디에 있든 주변 환경에서 시간당 1마이크로시버트의 방사선을 계속 받는다. 게다가 섬 자체도 방사능을 띠고 있어서, ii번째 섬으로부터 시간당 Di2D_i^{-2}마이크로시버트의 방사선을 추가로 계속 받는다. 여기서 DiD_i는 현재 위치와 ii번째 섬 사이의 거리(킬로미터)이다. (엄밀히 말하면, 시각 tt에서 ii번째 섬까지의 거리를 Di(t)D_i(t), 여행에 걸린 전체 시간을 XX라고 할 때, ii번째 섬으로부터 받는 방사선의 총량은 정적분 0XDi(t)2dt\int_0^X D_i(t)^{-2}\,dt이다.) 섬의 좌표와 정확히 같은 점만 아니라면 섬에 얼마든지 가까이 다가갈 수 있다.

경로를 최적으로 정했을 때 받는 방사선 총량의 최솟값을 구하시오.

입력

첫째 줄에 테스트 케이스의 수 TT가 주어지고, 그 뒤로 TT개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 정수 NN과 실수 AA, BB가 주어진다. 둘째 줄에는 실수 NNCiC_i가 주어지며, ii번째 수는 ii번째 섬의 yy 좌표이다.

모든 실수는 소수점 아래 정확히 두 자리까지 주어진다.

제한

  • 1T201 \le T \le 20
  • 1N21 \le N \le 2
  • 10.00A10.00-10.00 \le A \le 10.00
  • 10.00B10.00-10.00 \le B \le 10.00
  • 모든 ii에 대해 10.00Ci10.00-10.00 \le C_i \le 10.00
  • iji \ne j이면 CiCjC_i \ne C_j

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 여행을 마칠 때까지 받는 방사선 총량의 최솟값(마이크로시버트)이다.

y는 소수점 아래 셋째 자리에서 반올림하여 소수점 아래 정확히 두 자리로 출력한다.

힌트

아래 그림은 예제 1의 첫 번째 테스트 케이스에서 최적 경로를 나타낸 것이다. 잘 보이도록 섬을 크게 그렸지만, 실제로는 하나의 점으로 취급한다는 점에 주의하라.