시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 10 5 2 66.667%

문제

공장에서 작업을 하는 로봇은 고정 축 F, 한 개의 관절 A, 두개의 뼈대 B, C와 손 D로 구성되어 있다. 그림 1과 같이 고정축 F는 공장 내부의 한 점에 고정되어 있고, 뼈대 B는 고정축 F와 관절 A사이를 연결하고, 다른 뼈대 C는 관절 A와 손 D사이를 연결한다.

그림 1

단, 뼈대 B와 C는 그림 2와 같이 다음 조건을 만족하면서 움직일 수 있다.

  1. 뼈대 B는 고정축에서 왼쪽 또는   오른쪽 수평방향으로 나오거나, 고정 축에서 위쪽 또는 아래쪽 수직방향으로 나올 수 있다.
  2. 뼈대 C는 관절 A에서 뼈대 B와 항상 수직을 이루면서 나온다.
  3. 뼈대 B와 C는 길이를 0에서 얼마든지 자유자재로 연장할 수 있다.


그림 2

로봇의 고정축이 위치한 공장은 그림 3과 같이 수평 방향과 수직 방향의 벽들이 번갈아 가면서 연결되어 있는 하나의 다각형으로 구성되어 있다. 따라서, 이 공장의 내부에는 벽들이 존재하지 않는다. 이 공장 내부의 어떤 위치에 로봇의 고정축 F를 고정시켰을 때, 위의 세 가지 조건들을 만족하면서 뼈대 B와 C의 위치와 길이를 조절하더라도 로봇의 손 D가 미치지 못하는 공장 내부의 지점이 있을 수 있다.

그림 3

그림 3의 예에서 로봇의 고정축이 P지점에 고정되어 있으면 공장 내부의 모든 위치에 로봇 손 D가 접근할 수 있지만, Q지점에 고정되어 있으면 로봇 손 D가 도달할 수 없는 지점(빗금 친 부분)이 존재한다.

공장의 경계를 나타내는 다각형의 꼭지점과 로봇의 고정축의 위치가 주어질 때, 공장의 내부에 로봇 손이 도달하지 못하는 부분이 있는 지를 검사하는 프로그램을 작성하시오. 단, 고정축은 공장의 내부에 존재하며, 공장의 내부는 경계선을 포함하지 않는다. 뼈대 B, C는 공장의 경계선을 따라 움직일 수 있고,  고정축, 관절과 손은 점으로, 뼈대는 두께가 없는 선분으로 가정한다.

 

그림 4

입력

첫째 줄에 공장의 경계를 나타내는 꼭지점의 개수 N이 주어진다. 단, 4≤N≤20,000이다. 다음 줄부터 N개의 꼭지점의 좌표와 5개의 로봇 고정축의 좌표가 다음과 같이 주어진다: 둘째 줄부터 N개의 줄에 꼭지점의 좌표 (X, Y)를 나타내는 두 개의 정수 X, Y가 한 줄에 하나씩 빈 칸을 사이에 두고 주어진다. 꼭지점의 좌표는 다각형 경계선의 반시계방향 순서로 주어지고, 모든 좌표의 값은 0이상 1,000,000 이하의 정수이다. 이어서 다음  5개의 줄에  로봇의 고정축의 좌표 (X, Y)를 나타내는 두 개의 정수 X, Y가 한 줄에 하나씩 빈 칸을 사이에 두고 주어진다.

출력

입력에서 주어진 5개 고정축의 각 위치에 대하여 로봇 손이 공장 내부의 모든 위치에 접근할 수 있는지 여부를 다음과 같이 차례대로 출력한다. 첫째 줄부터 k번째 줄에 입력에서  k번째 주어진 로봇의 고정축의 위치에 대하여 로봇 손이 공장 내부 전체에 접근할 수 있으면 YES를, 아니면 NO를 대문자로  출력한다.

예제 입력

8
0 0
20 0
20 20
30 20
30 0
40 0
40 40
0 40
10 10
25 30
35 10
5 30
10 20

예제 출력

NO
YES
NO
YES
YES

힌트

예제는 림 4를 참고한다.