DON'T PANIC!
시간 제한8초메모리 제한512 MB
구면 위의 다각형(대륙)과 착륙 지점이 주어질 때, 변이 최단 대권 호인 다각형 내부에 점이 있는지 판정한다.
문제
아서는 지구에 살던 순진한 남자다. 지구가 외계인에 의해 파괴되던 날까지 그는 아주 평범하게 살고 있었다. 그 외계인들은 사악한 침략자가 아니라 초공간 우회로를 건설하라는 명령을 받은 하청업체일 뿐이었다. 그들이 지구를 향해 철거 광선을 쏘던 순간, 아서는 자기 집 앞에 있었고 하마터면 수소, 산소, 탄소와 몇 가지 다른 원자로 분해될 뻔했다. 그러나 운 좋게도 그는 살아남았다. 그의 친구 포드는 사실 외계인으로, 우주 일주 여행 중에 지구에 들렀던 사람이었는데, 광선이 그에게 닿기 직전에 그를 우주선으로 끌어올렸다.
아서와 포드는 무사히 탈출했지만 그것은 고난의 시작일 뿐이었다. 곧 그 우주선이 바로 그 하청업체의 것이었다는 사실이 드러났고, 짐작할 수 있듯이 그들은 인간을 싫어했다. 그래서 아서와 포드를 발견하자마자 그들은 가장 가까운 미탐사 행성에 정박해, 불쌍한 두 사람을 지표면 위 10마일에서 우주선 밖으로 내던졌다.
다시 위기에 처했다! 다행히 우리의 영웅 포드에게는 낙하산이라는, 행성에 안전하게 착륙할 수 있게 해 주는 특별한 물건이 있으므로 그것은 걱정하지 않아도 된다. 문제는 그들이 그저 자유낙하 중이라 착륙 지점을 바꿀 수 없고, 그 지점이 육지일 수도 바다일 수도 있다는 것이다. 그들은 평화롭게 착륙할 수 있는지, 아니면 가장 가까운 해안까지 헤엄쳐야 하는지 알고 싶어 한다.
포드의 만능 GPS 기기는 착륙 예상 위치를 위도와 경도로 표시한다. 또 그는 우주의 거의 모든 행성을 설명하는 안내서를 가지고 있다. 그 책에 따르면 이 행성에는 대륙이 하나뿐이므로 바다도 하나뿐이다. 책에는 대륙의 모양에 대한 설명도 있지만, 아쉽게도 그림 지도처럼 직관적인 방식은 아니다. 그래서 당신의 임무는 그 지점이 육지 위에 있는지 아닌지를 판정하는 프로그램을 만드는 것이다.
입력
N
P0 T0
.
.
.
PN TN
입력의 첫째 줄에는 정수 N (3 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 아서와 포드가 착륙할 지점의 위도와 경도를 나타내는 두 정수 P0, T0이 주어진다. 다음 N개 줄은 이 행성의 유일한 대륙의 모양을 설명한다. k번째 줄에는 점 Vk의 위도와 경도를 나타내는 두 정수 Pk, Tk가 주어진다. 대륙은 구 위의 N개 꼭짓점 Vk로 이루어진 다각형으로 설명된다. 해안선은 연속한 두 점을 최단선으로 이어 붙여 이루어진다.
(Pk, Tk) (k = 0, 1, ...., N)는 -90 ≤ Pk ≤ 90, -180 ≤ Tk ≤ 180을 만족한다. 위도가 양수면 북쪽, 음수면 남쪽이다. 경도가 양수면 동쪽, 음수면 서쪽이다. 대륙의 경계는 반시계 방향으로 주어지며, 주어진 연속한 두 점을 최소 거리로 잇는 방법은 항상 정확히 하나이고 대륙의 모양은 자기 교차하지 않는다고 가정할 수 있다. 착륙 지점은 해안선 위에 있지 않다.
출력
아서와 포드가 대륙에 착륙하게 된다면 “Yes”를 출력한다. 그렇지 않으면 “No”를 출력한다.