우주 골프

행성 표면을 탐사하는 새로운 방식으로 관측 탄환이라고 부르는 발사체를 쓴다. 탄환에는 스스로 움직이는 장치가 없고, 그래서 로버형 탐사 장비보다 비용이 훨씬 적게 든다.

탄환은 발사기에서 초기 속도를 받아 튀어 나간 다음, 지면에 닿을 때까지 포물선을 그린다. 지면에서 튕기면 다시 포물선을 그리고, 이 과정을 사실상 무한히 반복한다.

우리는 탄환이 행성 표면의 목표 지점에서 정확히 튕기도록 초기 속도를 맞추려고 한다. 튕기는 순간에 탄환 안의 여러 센서가 자료를 모아 관측 기지로 보낸다. 보통의 표적 사격처럼 들리지만 어려운 점이 몇 가지 있다.

• 발사기와 목표 지점 사이에 장애물이 있을 수 있다. 장애물은 지면에 수직으로 서 있고, 두께는 무시할 만큼 얇다. 탄환이 장애물에 한 번 닿으면 그 뒤의 궤적을 알 수 없으므로, 장애물에 닿지 않도록 발사를 계획해야 한다.
• 충분히 빠른 속도로 거의 수직으로 쏘면 장애물에 닿지 않고 목표를 맞히기 쉽지만, 초기 속력이 크면 에너지를 많이 쓴다. 우주 탐사에서 에너지는 매우 귀하므로 탄환의 초기 속력을 최소로 해야 한다. 탄환을 여러 번 튕기게 하면 더 낮은 초기 속력으로 목표에 도달한다.
• 그렇지만 탄환이 튕기는 횟수는 주어진 값을 넘을 수 없다. 탄환의 몸체는 충분히 튼튼하지만, 안에 든 센서 가운데 일부가 반복되는 충격을 견디지 못한다. 허용되는 튕김 횟수는 관측 탄환의 종류마다 다르다.

임무를 완수하는 데 필요한 최소 초기 속력을 구하는 프로그램을 작성하라.

다음을 가정한다.

• 행성의 대기가 매우 희박해서 공기 저항은 무시한다.
• 행성이 충분히 커서 표면은 완전한 평면으로 본다.
• 중력 가속도는 탄환이 도달하는 가장 높은 지점까지 일정하다고 본다.

따라서 탄환은 완전한 포물선 궤적을 따라 난다.

다음도 가정한다.

• 행성 표면과 탄환이 매우 단단해서 튕김은 탄성 충돌로 본다. 즉 튕길 때 잃는 운동 에너지는 무시한다. 공기 저항도 무시하므로 튕긴 직후의 속도는 발사 직후의 속도와 같다.
• 탄환은 충분히 작아서 크기를 무시한다.
• 발사기도 충분히 작아서 높이를 무시한다.

강체 운동의 기본을 정리한다.

탄환의 속도 $v$를 수평 성분 $v_x$와 수직 성분 $v_y$로 나누어 쓴다. 위쪽이 양수다. 초기 속도의 성분은 $v_{ix}$와 $v_{iy}$이고, 발사 직후에는 $v_x = v_{ix}$, $v_y = v_{iy}$가 성립한다. 시각 $t$에서 발사기로부터의 수평 거리를 $x$, 고도를 $y$로 쓴다.

공기 저항을 무시하면 수평 속도 성분은 비행 내내 일정하다. 그래서 발사기로부터의 수평 거리는 흐른 시간에 비례한다.

$x = v_{ix} t$

수직 속도 성분 $v_y$는 중력 때문에 점점 줄어든다. 중력 가속도가 $g$일 때 비행 중에 다음 미분 방정식이 성립한다.

$\frac{dv_y}{dt} = -g$

$t = 0$일 때 $v_y = v_{iy}$, $y = 0$이라는 초기 조건으로 풀면 다음을 얻는다.

$y = -\frac{1}{2} g t^2 + v_{iy} t = -\left( \frac{1}{2} g t - v_{iy} \right) t$

이 식은 탄환이 $t = 2 v_{iy} / g$에 다시 지면에 닿는다는 뜻이다. 그러므로 튕기는 지점은 발사기에서 $2 v_{ix} v_{iy} / g$만큼 떨어져 있다. 다시 말해 탄환을 거리 $l$만큼 날리려면 초기 속도의 두 성분이 $2 v_{ix} v_{iy} = l g$를 만족해야 한다.

위 두 식에서 매개변수 $t$를 없애면 탄환의 포물선 궤적을 나타내는 식을 얻는다.

$y = -\frac{g}{2 v_{ix}^2} x^2 + \frac{v_{iy}}{v_{ix}} x$

계산을 쉽게 하려고 이 문제는 특별한 단위계를 쓴다. 이 단위계에서 행성의 중력 가속도 $g$는 정확히 1.0이다.

입력은 테스트 케이스 하나로 이루어지며, 형식은 다음과 같다.

d n b
p1 h1
p2 h2
.
.
.
pn hn

첫 줄에 정수 $d$, $n$, $b$가 주어진다. $d$는 발사기에서 목표 지점까지의 거리이고 ($1 \le d \le 10000$), $n$은 장애물의 개수이며 ($1 \le n \le 10$), $b$는 허용되는 최대 튕김 횟수다 ($0 \le b \le 15$). 목표 지점에서 튕기는 것은 이 횟수에 넣지 않는다.

이어지는 $n$개 줄에는 각각 정수가 두 개 있다. $k$번째 줄의 $p_k$는 $k$번째 장애물의 위치, 즉 발사기로부터의 거리이고, $h_k$는 지면에서 잰 높이다. $k = 1, \dots, n-1$에 대해 $0 < p_1$, $p_k < p_{k+1}$이고, $p_n < d$이다. 또 $k = 1, \dots, n$에 대해 $1 \le h_k \le 10000$이다.

탄환을 목표 지점에 도달하게 하는 가장 작은 초기 속력 $v_i$를 출력한다. 탄환의 초기 속력은 다음과 같이 정의한다.

$v_i = \sqrt{v_{ix}^{2} + v_{iy}^{2}}$

값을 소수점 아래 여섯째 자리에서 반올림해서, 소수점 아래 자리가 정확히 다섯 개인 형태로 한 줄에 출력한다.