점과 볼록 다각형 포함 관계

점과 볼록 다각형 포함 관계

볼록 다각형과 한 점이 주어질 때, 점이 다각형의 내부, 경계, 외부 중 어디에 있는지 판별하라.

다각형의 꼭짓점은 반시계 방향 순서로 주어진다. 볼록 다각형은 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형이다.

입력

첫째 줄에 다각형의 꼭짓점 수 N이 주어진다.
둘째 줄부터 N개 줄에 걸쳐 각 꼭짓점의 x, y 좌표가 한 줄에 하나씩 반시계 방향 순서로 주어진다.
N+2번째 줄에 판별할 점의 x, y 좌표가 주어진다.

제한

• 3 ≤ N ≤ 100,000
• -10^9 ≤ x, y ≤ 10^9
• 모든 좌표는 정수이다.
• 꼭짓점이 일직선 위에 놓이는 경우는 없다.

출력

점이 다각형의 내부에 있으면 INSIDE, 경계에 있으면 BOUNDARY, 외부에 있으면 OUTSIDE를 출력한다.

예제 입력 1

4
0 0
4 0
4 4
0 4
2 2

예제 출력 1

INSIDE

예제 입력 2

4
0 0
4 0
4 4
0 4
0 0

예제 출력 2

BOUNDARY