아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

DON'T PANIC!

시간 제한8초메모리 제한512 MB

요약
구면 위의 다각형(대륙)과 착륙 지점이 주어질 때, 변이 최단 대권 호인 다각형 내부에 점이 있는지 판정한다.
난이도

보통10점 중 7점

유형
기하, 수학, 구현
정답자
아직 제출이 없습니다

문제

아서는 지구에 살던 순진한 남자다. 지구가 외계인에 의해 파괴되던 날까지 그는 아주 평범하게 살고 있었다. 그 외계인들은 사악한 침략자가 아니라 초공간 우회로를 건설하라는 명령을 받은 하청업체일 뿐이었다. 그들이 지구를 향해 철거 광선을 쏘던 순간, 아서는 자기 집 앞에 있었고 하마터면 수소, 산소, 탄소와 몇 가지 다른 원자로 분해될 뻔했다. 그러나 운 좋게도 그는 살아남았다. 그의 친구 포드는 사실 외계인으로, 우주 일주 여행 중에 지구에 들렀던 사람이었는데, 광선이 그에게 닿기 직전에 그를 우주선으로 끌어올렸다.

아서와 포드는 무사히 탈출했지만 그것은 고난의 시작일 뿐이었다. 곧 그 우주선이 바로 그 하청업체의 것이었다는 사실이 드러났고, 짐작할 수 있듯이 그들은 인간을 싫어했다. 그래서 아서와 포드를 발견하자마자 그들은 가장 가까운 미탐사 행성에 정박해, 불쌍한 두 사람을 지표면 위 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”를 출력한다.

예제3

  1. 예제 1

    입력
    4
    0 0
    10 10
    10 -10
    -10 -10
    -10 10
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    4
    89 0
    0 0
    0 90
    0 180
    0 -90
    
    예상 출력
    Yes
    
  3. 예제 3

    입력
    4
    89 0
    0 0
    0 -90
    0 180
    0 90
    
    예상 출력
    No