대권 항로

시간 제한1초메모리 제한128 MB

요약

두 도시의 위도와 경도를 도, 분 단위로 받아 두 지점을 잇는 대권 항로에서 가장 북쪽에 이르는 위도를 구하고, 유일하지 않으면 undefined를 출력한다.

문제

비행기는 두 도시를 잇는 대권 항로(great circle route)에 가깝게 비행한다. 대권 항로란 지구의 중심을 공유하는 대원(大圓) 위에서 두 도시를 잇는 가장 짧은 호, 즉 지표면을 따라 잰 두 도시 사이의 최단 경로이다.

두 도시의 위도와 경도가 주어질 때, 두 도시를 잇는 대권 항로가 도달하는 가장 북쪽(최대) 위도를 구하여라. 답이 유일하지 않으면 undefined를 출력한다.

첫째 줄에 테스트 케이스의 수 $N$ 이 주어진다. 이어지는 $N$ 개의 줄에는 각 케이스가 공백으로 구분된 네 개의 토큰 lat1 lon1 lat2 lon2으로 주어지며, 두 도시의 위도와 경도를 도(degree)·분(minute)·방향으로 나타낸다.

위도 토큰은 도,분D 형식이며 D는 N 또는 S이다. 경도 토큰은 도,분D 형식이며 D는 E 또는 W이다. 1분은 $1/60$ 도이다.

표기 약속: 적도 위의 점은 위도를 0,0N으로 적는다(0,0S가 아니다). 극점의 경도는 0,0W로 적는다. 경도가 180도인 점은 180,0W로 적는다(180,0E가 아니다).

각 테스트 케이스마다 도달하는 가장 북쪽 위도를 같은 도,분D 형식으로, 가장 가까운 분 단위로 반올림하여 한 줄에 출력한다. 답이 유일하지 않으면 undefined를 출력한다.

예제 1

입력

3
50,13N 45,10W 75,0N 44,50E
50,13N 90,10W 75,0N 89,50E
10,0N 129,30E 10,0S 50,30W

예상 출력

75,41N
90,0N
undefined