[백준 - 4167] Tunnelling the Earth - Python

분류: 수학, 3차원 좌표계 /

 

문제

문제 링크

문제 설명

There are different methods of transporting people from place to place: cars, bikes, boats, trains, planes, etc. For very long distances, people generally fly in a plane. But this has the disadvantage that the plane must fly around the curved surface of the earth. A distance travelled would be shorter if the traveller followed a straight line from one point to the other through a tunnel through the earth.

For example, travelling from Waterloo to Cairo requires a distance of 9293521 metres following the great circle route around the earth, but only 8491188 metres following the straight line through the earth.

For this problem, assume that the earth is a perfect sphere with radius of 6371009 metres.

입력

The first line of input contains a single integer, the number of test cases to follow. Each test case is one line containing four floating point numbers: the latitude and longitude of the origin of the trip, followed by the latitude and longitude of the destination of the trip. All of these measurements are in degrees. Positive numbers indicate North latitude and East longitude, while negative numbers indicate South latitude and West longitude.

출력

For each test case, output a line containing a single integer, the difference in the distance between the two points following the great circle route around the surface of the earth and following the straight line through the earth, in metres. Round the difference of the distances to the nearest integer number of metres.

 

풀이

from math import cos, sin, acos, sqrt, pi as PI
import sys
read = sys.stdin.readline

def latLon2xyz(lat, lon):
    cosLat = cos(lat)
    return [cosLat*cos(lon), cosLat*sin(lon), sin(lat)]

def product(dimension, coord1, coord2):
    result = 0
    for i in range(dimension):
        result += coord1[i] * coord2[i]
    return result

def main():
    R = 6371009
    T = int(read())
    for _ in range(T):
        lat1, lon1, lat2, lon2 = map(
            lambda x: float(x) * PI / 180, read().split())
        origin = latLon2xyz(lat1, lon1)
        destination = latLon2xyz(lat2, lon2)
        cosTheta = product(3, origin, destination)
        theta = acos(cosTheta)
        straight = sqrt(2 - 2 * cosTheta)
        result = R * (theta - straight)
        print(round(result))

main()

구면 상의 서로 다른 두 점을 지나는 대원(great circle)은 항상 존재하며 대원 위 경로가 최단 거리다.

사실상 문제는 2차원 원의 호의 길이와 현의 길이의 차이를 구하는 문제다.

두 점의 최단 거리를 포함하는 부채꼴의 중심각(𝜽)을 구하면 쉽게 풀린다.

경위도 좌표계로 나타난 P(𝝀, 𝝋)를 직각좌표계 P(x, y, z)로 변환한 뒤 두 벡터에 대한 단위벡터의 내적으로 중심각을 계산한다.

여기서 주의할 점은 입력이 호도법이 아닌 육십분법으로 주어진다.

파이썬에서 삼각함수의 입출력은 호도법이다.

중심각을 알면 호와 현의 길이를 계산할 수 있다.

0 ≤ 𝜃 ≤ 𝜋 이므로 0 ≤ sin(𝜃/2) ≤ 1이다. 따라서 마지막에 제곱근을 계산할 때 양수만 취한다.