GPS

여러분도 다른 많은 사람들처럼 위성 항법 장치(GPS)를 사용해 봤겠지만, 그것이 실제로 어떻게 동작하는지는 궁금했을 것이다. GPS 위치 측정은 지구를 도는 위성들의 집합을 바탕으로 한다. 모든 위성은 동기화된 내부 시계를 가지고 있다.¹ 위성들은 자신의 내부 시계 값을 전파를 통해 지구 표면으로 계속 전송한다. GPS 수신기는 시야에 들어온 일부 위성으로부터 측정값을 동시에² 수집한다. 시각 t에 수집된 시간 측정값 t1, ..., tm은 각 위성까지의 거리가 다르기 때문에 일반적으로 서로 다르다. 모든 위성의 정확한 궤도를 알고 있으므로, 각 위성이 신호를 보낸 순간 어디에 있었는지도 정확히 알 수 있다. 이 위치들과 거리를 바탕으로 자신의 위치를 계산할 수 있다. 지구 표면에 있다고 가정할 때 고유한 위치를 계산하려면 위성으로부터 최소 3개의 측정값이 필요하다.

그러나 이 문제의 과제는 자신의 위치를 실제로 계산하는 것이 아니라, 어떤 신호를 어떤 위성으로부터 받았는지 판별하는 것이다. 정확히 말하면, 지구에서의 자신의 지리 좌표와 모든 위성의 궤도에 대한 설명이 주어지며, 각 위성에 대해 다음을 판별해야 한다.

• 특정 시각에 위성에서 보낸 신호가 여러분에게 도달하는지 여부. 신호가 지구를 통과하지 않으면 도달한다.
• 신호가 도달한다면, 신호가 위성에서 여러분의 위치까지 이동하는 데 걸린 시간.

전파는 직선으로 이동하며 빛의 속도로 진행한다고 가정하고, 빛의 속도는 299 792 458 미터 매 초로 둔다. 지구는 반지름 6 371km인 완전한 구이며, 모든 GPS 위성은 중심이 지구 중심과 일치하는 완전한 원 궤도를 일정한 속도로 돈다고 가정한다.

¹실제로는 일반 상대성 이론 때문에 시계가 완전히 동기화되지 않는다. 이 문제에서는 이러한 효과가 존재하지 않는다고 가정한다.

²또 하나의 단순화다.

입력은 다음과 같이 구성된다.

• 정수 s (1 ≤ s ≤ 10⁴)가 있는 한 줄. s는 위성의 수다.
• 두 실수 ℓo, ℓa가 있는 한 줄. 각각 여러분의 위치의 경도와 위도다.
• s개의 줄. 각 줄에는 네 실수 φ, ψ, r, x가 있으며 위성 하나를 나타낸다.

경도 ℓo ∈ [−180, 180]에서 양수는 동쪽, 음수는 서쪽을 나타낸다. 위도 ℓa ∈ [−90, 90]에서 양수는 북쪽, 음수는 남쪽을 나타낸다.

위성 설명의 형식은 다음과 같다.

• φ ∈ [−180, 180] – 궤도가 지구 적도와 만나는 기준 경도다. 각 궤도는 적도와 (적어도) 두 번 만난다. 양수 경도는 동쪽, 음수 경도는 서쪽을 나타낸다.
• ψ ∈ [0, 360] – 경도 φ에서 적도를 지날 때 궤도와 지구의 동쪽 방향 적도 사이의 각도다. 0에서 180 사이의 값은 북쪽으로 향하는 이동을, 180에서 360 사이의 값은 남쪽으로 향하는 이동을 나타낸다. 궤도가 적도와 동일 평면에 있으면 각도 ψ는 0 또는 180이다.
• r ∈ [7 000, 10⁶] – 위성 궤도의 반지름을 킬로미터 단위로 나타낸 값이다.
• x ∈ [0, 1) – 신호를 보낸 시각에 위성이 φ에서 적도와 만나는 지점을 기준으로 궤도를 얼마나 진행했는지를 나타내는 비율이다.

그림 G.1: 위성 좌표를 도식으로 나타낸 그림. 위성의 궤도는 빨간색으로, 위성의 실제 위치는 빨간 점으로 표시되어 있다. 지구에는 적도와 본초 자오선이 선으로 표시되어 있다. 점선은 적도와 동일 평면에 있고 위성 궤도와 반지름이 같다. 각도 φ와 ψ는 입력 절에서 설명한다. 검은 점은 지구에서의 여러분의 위치이며, 파란 선을 따라 신호가 이동하는 데 필요한 시간을 계산해야 한다.

참고: 입력의 모든 실수는 소수점 이하 최대 3자리까지 주어진다. 각 위성은 여러분의 위치에서의 접평면으로부터 최소 1미터 이상 떨어져 있음이 보장된다. 따라서 해법에서 부동 소수점 연산을 안전하게 사용할 수 있다.

각 위성에 대해, 그 위성에서 보낸 신호가 여러분에게 도달하지 않으면 no signal을 출력한다. 위성의 신호가 여러분에게 도달하면, 신호가 위성에서 여러분의 위치까지 이동하는 데 필요한 시간을 초 단위로 출력한다. 시간은 상대 오차 또는 절대 오차 중 더 낮은 값 기준으로 10−7 이내의 정확도를 가져야 한다.