배가 (-10, A)에서 (10, B)까지 시속 1km로 이동할 때, 기본 1마이크로시버트와 각 섬 (0, C_i)에서의 1/D^2 방사선을 합한 최소 선량을 구한다.
어려움8기하수학그리디구현아직 제출이 없습니다시간 제한30초메모리 제한512 MB배를 몰아 좌표 (−10,A)에서 좌표 (10,B)까지 가려고 한다. 좌표의 단위는 킬로미터이고, 배는 시속 1킬로미터의 일정한 속력으로 움직인다. 배가 지나갈 경로는 마음대로 정할 수 있다. 배는 하나의 점으로 생각한다.
이 해역에는 섬이 N개 있고, 각 섬도 하나의 점으로 생각한다. i번째 섬은 좌표 (0,Ci)에 있다.
해역 전체가 방사능에 오염되어 있어서, 어디에 있든 주변 환경에서 시간당 1마이크로시버트의 방사선을 계속 받는다. 게다가 섬 자체도 방사능을 띠고 있어서, i번째 섬으로부터 시간당 Di−2마이크로시버트의 방사선을 추가로 계속 받는다. 여기서 Di는 현재 위치와 i번째 섬 사이의 거리(킬로미터)이다. (엄밀히 말하면, 시각 t에서 i번째 섬까지의 거리를 Di(t), 여행에 걸린 전체 시간을 X라고 할 때, i번째 섬으로부터 받는 방사선의 총량은 정적분 ∫0XDi(t)−2dt이다.) 섬의 좌표와 정확히 같은 점만 아니라면 섬에 얼마든지 가까이 다가갈 수 있다.
경로를 최적으로 정했을 때 받는 방사선 총량의 최솟값을 구하시오.
첫째 줄에 테스트 케이스의 수 T가 주어지고, 그 뒤로 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 정수 N과 실수 A, B가 주어진다. 둘째 줄에는 실수 N개 Ci가 주어지며, i번째 수는 i번째 섬의 y 좌표이다.
모든 실수는 소수점 아래 정확히 두 자리까지 주어진다.
각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 여행을 마칠 때까지 받는 방사선 총량의 최솟값(마이크로시버트)이다.
y는 소수점 아래 셋째 자리에서 반올림하여 소수점 아래 정확히 두 자리로 출력한다.
아래 그림은 예제 1의 첫 번째 테스트 케이스에서 최적 경로를 나타낸 것이다. 잘 보이도록 섬을 크게 그렸지만, 실제로는 하나의 점으로 취급한다는 점에 주의하라.
