2395 : 다각형 안의 점
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 22 회
- 시도횟수
- 61 회
문제
단순 다각형이란, 볼록하거나 오목하기도 한 다각형이며, 다각형을 이루는 선이나 변이 서로 교차하지 않는 다각형을 뜻한다.
2차원 평면 좌표 상에서 임의의 한 점 (X,Y)와 단순 다각형을 이루는 꼭지점들이 주어졌을 때, (X,Y)가 다각형 안에 포함 되었는가 아닌가 혹은 다각형을 이루는 선분에 걸쳤는가를 판별하는 프로그램을 작성하라.
문제를 간단하게 하기 위해서 다각형을 이루는 모든 변은 좌표 축에 수직 혹은 수평하며, 다각형을 이루는 꼭지점의 좌표는 모두 정수 좌표이다. 입력된 다각형은 마지막으로 입력된 꼭지점을 제외하고, i번째로 입력된 꼭지점과 i+1번째로 입력된 꼭지점을 잇는 직선이 존재하며, 마지막 꼭지점은 맨 앞에 입력된 꼭지점과 이어져 있다.
입력형식
입력의 처음에는 다각형을 이루는 꼭지점의 개수를 뜻하는 정수 N(4≤N≤50)이 입력된다.
그 다음 줄부터 N개의 줄에는 다각형을 이루는 꼭지점의 위치를 의미하는 x, y가 입력된다.
x와 y는 -1,000이상 1,000이하의 정수다.
마지막 줄에는 위치를 판별하기 위한 점의 좌표 X와 Y가 입력된다.
출력형식
입력에 대해서 (X,Y)가 다각형의 내부에 위치하였을 경우에는 "INTERIOR"를,
외부에 위치했을 경우에는 "EXTERIOR"를,
다각형의 변(혹은 경계선)에 위치했을 경우에는 "BOUNDARY"를
출력한다(쌍따옴표 제외하여 출력).
입력 예4 0 0 0 10 10 10 10 0 5 5 |
출력 예INTERIOR |
입력 예12 0 0 0 1000 1000 1000 1000 800 200 800 200 600 600 600 600 400 200 400 200 200 1000 200 1000 0 100 500 |
출력 예INTERIOR |
입력 예4 0 0 0 10 10 10 10 0 5 10 |
출력 예BOUNDARY |
입력 예4 0 0 0 10 10 10 10 0 10 15 |
출력 예EXTERIOR |