수정사항

1. 2022.02.06. 박원님 께서 실수 연산 오차로 인하여 비교를 위해서는 abs(mid-L) < epsilon 형식으로 하는 것이 더 타당하다고 지적해 주셨습니다. 이를 받아들여, 도착지점을 구하는 의사코드에서 비교 부분 (mid == L)을 수정하였습니다.

문제

이 문제는 다른 알고리즘 문제와 달리, 물리학 지식이 요구된다. 고등학교 물리학2나 대학교 일반물리학1에서 역학 부분을 잘 이해하고 있다면, 방정식을 세울 수 있다. 이러한 방정식을 세우고 값을 구할 때, 문제의 오차 범위 내에서 구하면 되기 때문에, 정확한 값을 구할 필요는 없다. 즉, 수치 해석적 방법(예, 이분 탐색, 뉴튼-랩슨 법)을 추가적으로 이해한다면 방정식으로 부터 문제를 해결할 수 있다. 문제를 단계로 나누어서 구하여 보자.

1. 선수가 활강할 때 시작 속력을 구하기
2. 선수가 낙하하면서 그리는 궤적함수 구하기
3. 선수가 언덕과 만나는 도착 지점 구하기
4. 선수의 도착시 속도를 구하기
5. 선수의 도착시 각도를 구하기 여기서 우리가 받는 입력은, 활강을 위한 높이 j, 슬로프를 결정하는 변수 p,H,L이다.

초기속력 구하기

선수가 활강을 시작할 때, 초기 속력을 우선 구하여 보자. 주어진 좌표계에서, $P_0 = (0, H+p)$에서 속력을 구하면 된다. 출발에서 초기 위치 에너지가 모두 운동 에너지로 전환이 되는 상황이다. 방정식을 세우면 아래와 같다.

\[mgj = \frac{1}{2} m {v_0}^2\]

여기서 $m$은 선수의 질량, $g$는 중력가속도, $v_0$는 초기 속력이다. $P_0$에서 접선은 X축과 평행하므로, Y축의 초기 속도는 0이라 볼 수 있다. 그러면 초기 속력은 $v_0 = (\sqrt{2gj}, 0)$임을 알 수 있다.

선수의 궤적함수 그리기

선수가 활강을 시작한 이후 운동을 생각하여 보자. X축과 Y축 방향 운동을 따로 보자면, X축은 마찰과 공기저항을 무시하여 등속운동을 할 것이다. Y축은 중력에 의하여 등가속도 운동을 하게 될 것이다. 각각의 시간 $t$에 따른 위치를 구하여 보자. 우선 X축 운동의 경우,

\[x = v_0 t = \sqrt{2gj}t\]

다음으로 Y축 운동의 경우,

\[y = H + p - \frac{1}{2}gt^2\]

두 수식을 도출할 수 있다. 즉 시간 $t$에서 선수의 위치는 $P = (\sqrt{2gj}t,H + p - \frac{1}{2}gt^2)$이다.

도착 지점 구하기

도착 지점의 경우 언덕이 그리는 함수와 만나는 지점이다. 만나는 X축 값을 우리는 $l$이라 부르기로 하자. X축에서 만남과 Y축에서 만남을 수식으로 나타내면, 아래와 같다.

\[l = \sqrt{2gj}t \\ h(l) = H + p - \frac{1}{2}gt^2\]

변수 $t$를 첫 번째 X축에 대한 방정식에 있는 $l$로 치환하면, 아래와 같다.

\[h(l) = H + p - \frac{1}{2}g\left(\frac{l}{\sqrt{2gj}}\right)^2 = H + p - \frac{l^2}{4j}\]

$H + p - \frac{l^2}{4j} - h(l) = 0$의 해를 구하는 과정이라 볼 수 있다. 여기서는 단순한 이분 탐색을 생각하여 보자. 해를 구하고자 하는 방정식의 값은 $l$이 증가함에 따라 감소하는 것을 관찰할 수 있다. 이를 이분탐색으로 적용한다면, 중간값 mid를 $l$에 대입하고 그 결과값을 diff에 저장한다. 만약 diff가 0보다 크다면 해는 우측에 있을 것이므로 left 값을 mid로 설정한다. 반대로 diff가 0보다 작다면 해는 좌측에 있을 것이므로 right 값을 mid로 설정한다. 그렇지만 완벽히 0인 값을 얻을 필요는 없다. 우리는 오차범위 내 적절한 값을 구하면 되는데, 이 경우 diff값의 절댓값이 $10^-6$ 보다 작으면 탐색을 종료하도록 설정하였다. 이럴 경우 코너에 발생되는 문제를 해결할 수 없다. 이는 활강을 마치고도 언덕과 마주치지 않는 경우다. 이 경우 탐색은 언덕의 끝에 도달하여 mid는 L과 같은 값을 가지게 된다. 언덕과 만나지 않는 경우의 값을 별도로 구하여보자. Y의 값은 0이 되므로, 아래 방정식의 해가 답이다.

\[0 = H + p - \frac{l^2}{4j} \\ l = 2 \sqrt{(H+p)j}\]

이를 코드로 표현하면 아래와 같다.

double search_l (void){
	double left, right, mid;
	double diff;
	double epsilon = 1e-6

	left = 0.0;
	right = L;
	
	while(left <= right){
		mid = (left + right) * 0.5;
		diff = player_h (mid) - slope (mid);
		if (abs(mid-L) < epsilon)
			return 2.0 * sqrt ((H+p)*j); 	
		}
		if (diff > 0.0){
			left = mid;
		}
		else {
			right = mid;
		}
	}
}

도착 속도 구하기

도착 지점 $l$로 부터 도착시 속도를 구하여보자. 선수의 시간에 따른 위치 $P = (\sqrt{2gj}t,H + p - \frac{1}{2}gt^2)$ 를 시간 $t$ 에 따라 미분하면 된다. $\dot{P} = (\sqrt{2gj},-gt)$ 가 된다. $t$와 $l$과 관련된 방정식은 위의 $t = \frac{l}{\sqrt{2gj}}$를 활용하여 치환하면 된다.

\[\mathbf{P} = \left(\sqrt{2gj},-g\frac{l}{\sqrt{2gj}}\right)\]

$\mathbf{P}$의 크기를 통하여 도착시 속도를 구할 수 있다.

도착 각도 구하기

도착시 각도는 언덕의 접선과 선수의 속력과의 내적을 통해 정의할 수 있다. 도착시 언덕의 접선벡터를 아래와 같이 구할 수 있다.

\[h = (l, h(l)) \\ \mathbf{h} = (1, \frac{dh}{dl}(l)) \\ \frac{dh}{dl}(l) = \left\{ \begin{array}{ll} 0 & l < 0 \\ -4H \frac{l}{L^2} & 0 \geq l < \frac{L}{2} \\ 4H \left(\frac{l}{L^2} - \frac{1}{L}\right) & \frac{L}{2} \geq l < L \\ 0 & L \geq l \end{array}\right.\]

접선과 속력의 내적을 통하여 각도는 아래 공식을 통해 구할 수 있다.

\[\theta = \arccos\left(\frac{\mathbf{P} \cdot \mathbf{h}}{|\mathbf{P}| \cdot |\mathbf{h}|}\right)\]