문제1636--Point In Polygon

1636: Point In Polygon

실행시간 제한: 5 Sec  메모리사용 제한: 128 MB
제출: 120  통과: 42
[제출] [채점기록] [묻고답하기]

문제 설명

Given a test point, (X, Y), and the vertices of a simple polygon, vertices, determine if the test point is in the interior, in the exterior or on the boundary of the polygon. Output the string "INTERIOR", "EXTERIOR", or "BOUNDARY".
For simplicity, all sides of the polygon will be horizontal or vertical, and the vertices and the test point will all be at integer coordinates. There is an edge from i-th vertex to (i+1)-th vertex for i from 0 to n-2, and an edge from (n-1)-th vertex to 0-th vertex where n is the number of vertices (and the number of edges) in the polygon.
A simple polygon is a polygon that may or may not be convex, but self-intersection is not allowed. Not even at a single point.

입력 설명

The first line of input contains the number of test cases T (T ≤ 100).

For each test case, the first line contains three integers N (4 ≤ N ≤ 50), X and Y (-1000 ≤ X, Y ≤ 1000).  

Following N lines will contain corresponding x- and y-coordinates for each vertex (-1000 ≤ xy ≤ 1000). No three consecutive vertices will be colinear.

출력 설명

For each test case, output a single line containing "INTERIOR", "EXTERIOR", or "BOUNDARY".

입력 예시 Copy

8
4 5 5
0 0
0 10
10 10
10 0
4 10 15
0 0
0 10
10 10
10 0
4 5 10
0 0
0 10
10 10
10 0
12 0 0
-100 -90
-100 100
100 100
100 -100
-120 -100
-120 100
-130 100
-130 -110
110 -110
110 110
-110 110
-110 -90
12 100 500
0 0
0 1000
1000 1000
1000 800
200 800
200 600
600 600
600 400
200 400
200 200
1000 200
1000 0
12 322 333
0 1000
1000 1000
1000 800
200 800
200 600
600 600
600 400
200 400
200 200
1000 200
1000 0
0 0
40 200 200
500 0
500 100
400 100
400 200
300 200
300 300
200 300
200 400
100 400
100 500
0 500
0 400
-100 400
-100 300
-200 300
-200 200
-300 200
-300 100
-400 100
-400 0
-500 0
-500 -100
-400 -100
-400 -200
-300 -200
-300 -300
-200 -300
-200 -400
-100 -400
-100 -500
0 -500
0 -400
100 -400
100 -300
200 -300
200 -200
300 -200
300 -100
400 -100
400 0
46 0 0
1 0
2 0
2 1
3 1
3 0
4 0
4 -1
5 -1
5 0
6 0
6 2
0 2
0 3
-1 3
-1 4
0 4
0 6
1 6
1 7
0 7
0 8
-2 8
-2 2
-8 2
-8 0
-7 0
-7 -1
-6 -1
-6 0
-4 0
-4 1
-3 1
-3 0
-2 0
-2 -6
0 -6
0 -5
1 -5
1 -4
0 -4
0 -3
-1 -3
-1 -2
0 -2
0 -1
1 -1

출력 예시 Copy

INTERIOR
EXTERIOR
BOUNDARY
EXTERIOR
INTERIOR
EXTERIOR
INTERIOR
INTERIOR

도움

  • Illustration for 4th test case
  • Illustration for 5th test case
  • Illustration for 7th test case
  • Illustration for 8th test case

출처/분류