다각형 안의 점 > 문제은행 : 정보올림피아드&알고리즘



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

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP