Alex가 옳다

2018 ACM ICPC 세계 결승을 보러 베이징(중국)으로 가는 여정의 첫 구간에서, 팀원인 Alex와 Timothy가 치열하게 논쟁했습니다. 주제는 워싱턴 DC에서 베이징까지 가는 13시간짜리 비행이었습니다. 비행기가 (a) 태평양 위를 서쪽으로 가는지, (b) 대서양 위를 동쪽으로 가는지, 아니면 (c) 북쪽으로 올라가 북극점을 지나 남쪽으로 내려가는지가 쟁점이었습니다. Alex는 이 비행이 북극점 근처를 지나는 것이 분명하다고 주장했습니다. 스스로 "기하학 마스터"라고 부르는 Timothy는 이를 터무니없다고 반박하며, 조종사가 그런 비효율적인 경로를 택할 리 없다고 말했습니다.

Timothy에게는 실망스럽게도, 워싱턴 DC에 도착하자 Alex는 항공 지도를 띄워 보였습니다. 그리고 Timothy, Arup, Eric(둘은 Timothy의 의견을 지지했습니다)에게 실제로 이번 비행이 북극점 가까이를 지나는 경로를 비행한다는 것을 증명했습니다.

지구상의 서로 다른 두 지점(도시)의 위치가 주어질 때, 두 도시 사이를 지구 표면을 따라 가장 짧게 비행하는 동안 비행기와 북극점 사이에서 달성되는 최소 유클리드 거리를 계산하고, Alex의 주장이 맞는지 판정하세요. 비행기는 항상 지구 표면 위의 한 점이며, 즉 고도가 없다고 가정합니다.

Alex의 주장은 다음과 같이 정의합니다. 최적(최단) 비행으로 지구를 도는 동안 비행기와 북극점 사이의 최소 유클리드 거리가, 출발점과 도착점 각각에서 북극점까지의 거리보다 엄격하게 작다.

두 점 $(x\_0, y\_0, z\_0)$과 $(x\_1, y\_1, z\_1)$ 사이의 유클리드 거리는 $\sqrt{(x\_0 - x\_1)^2 + (y\_0 - y\_1)^2 + (z\_0 - z\_1)^2}$로 정의합니다. 이는 지구 표면을 따라 이동해야 하는 호의 거리와 다릅니다.

참고로, 반지름이 $R$인 구면에서 위도와 경도를 직교 좌표로 바꾸는 식은 다음과 같습니다.

$x = R \times \cos{(latitude)} \times \cos{(longitude)}$

$y = R \times \cos{(latitude)} \times \sin{(longitude)}$

$z = R \times \sin{(latitude)}$

참고 사항:

• 계산에는 지구 반지름으로 $6\,371$ km를 사용하세요.
• 북극점은 위도 90도, 경도 0도에 있습니다.

입력의 첫 줄에는 Alex와 Timothy가 다녀온 여행의 수 $T$($1 \le T \le 500$)가 정수로 주어집니다. 각 여행은 두 줄의 입력으로 이루어집니다. 각 여행의 첫 줄에는 출발 도시의 위도 latitude와 경도 longitude가 공백으로 구분되어 주어집니다($-90 \le latitude < 90$; $-180 < longitude \le 180$). 두 값은 소수점 아래 정확히 6자리를 가집니다. 둘째 줄에는 같은 형식으로 도착 도시의 위도와 경도가 주어집니다.

출발 도시와 도착 도시는 서로 다른 위치에 있으며(북극점 위가 아님), 두 도시를 잇는 최단 비행 경로는 정확히 하나만 존재한다고 보장됩니다.

각 여행에 대해 두 줄을 출력합니다. 첫 줄에는 그 여행에서 옳았던 사람을 Alex 또는 Timothy로 출력합니다. 둘째 줄에는 출발 도시에서 도착 도시까지 비행하는 동안 비행기와 북극점 사이에서 달성되는 최소 유클리드 거리를 출력합니다. 답은 소수점 아래 정확히 6자리까지 출력하세요. 절대 오차 또는 상대 오차가 $10^{-6}$ km 이하이면 정답으로 인정합니다. 각 여행 뒤에는 빈 줄을 출력하세요.

참고 #1: 사용하는 프로그래밍 언어 라이브러리가 제공하는 원주율($\pi$) 값을 사용하세요.

참고 #2: Alex가 옳은 경우, 비행 경로를 따라 북극점까지의 최소 거리와 도착 지점까지의 최소 거리의 차이는 절댓값이 1 km 이상이라고 보장됩니다.