보로노이 다이어그램 점 판정

Figure: 크기 4인 보로노이 다이어그램.

2차원 직교 좌표계에서, 공집합이 아닌 점 집합 $S$의 보로노이 다이어그램을 "이 위치에서 $S$의 어느 점이 가장 가까운가?"라는 기준으로 평면을 나눈 그림으로 정의한다. 더 정확히는, 공집합이 아닌 점 집합 $\{P_1,\ P_2,\ \cdots,\ P_n\}$의 보로노이 다이어그램은 영역들의 모음이다. 점 $K$가 영역 $i$에 포함된다는 것은 모든 $1 \le j \le n$에 대해 $d(P_i,\ K) \le d(P_j,\ K)$가 성립한다는 것과 같다. 여기서 $d(X,\ Y)$는 점 $X$와 $Y$ 사이의 유클리드 거리이다.

예를 들어, 위 그림에서 평면의 모든 위치는 그 위치에서 가장 가까운 점에 따라 색이 칠해져 있다. 하나의 영역에만 속하는 점은 해당 영역을 나타내는 연한 색으로 칠해지고, 둘 이상의 영역에 속하는 점은 선과 점을 이루며 검은색으로 칠해진다.

보로노이 다이어그램을 $\mathcal{O}(n \log(n))$에 계산하는 알고리즘이 있지만, 매우 복잡하고 어렵기로 악명 높다. 우리는 관대한 출제자이므로 $n \leq 2000$으로 제한을 두었다. 느린 보로노이 다이어그램 알고리즘으로도 이 문제를 풀 수 있다.

이 문제에서는 보로노이 다이어그램의 점 판정 문제를 풀어야 한다. 점 집합 $\{P_1,\ P_2,\ \cdots,\ P_n\}$으로 만든 보로노이 다이어그램에서, 주어진 점이 어느 영역에 속하는지 판정한다. 더 정확히는 $q$개의 점 쿼리가 주어진다. 각 쿼리 점에 대해 다음을 판정한다.

• 어떤 영역에도 속하지 않으면 NONE을 출력한다.
• 정확히 하나의 영역에 속하면 REGION X를 출력한다. $X$는 그 영역의 번호이다.
• 정확히 두 영역에 속하면 LINE X Y를 출력한다. $X$와 $Y$($X$ < $Y$)는 그 두 영역의 번호이다.
• 세 개 이상의 영역에 속하면 POINT를 출력한다.

첫째 줄에 보로노이 다이어그램을 이루는 점의 개수 $n$과 쿼리의 개수 $q$가 주어진다. ($3 \le n \le 2,000,\ 1 \le q \le 250,000$)

다음 $n$개 줄의 $i$번째 줄에 $P_i$의 $x$ 좌표와 $y$ 좌표를 나타내는 두 정수가 주어진다. 이 점들이 보로노이 다이어그램을 이룬다. $n$개의 점은 모두 서로 다르다. ($|x|,\ |y| \le 10,000$)

다음 $q$개 줄의 $j$번째 줄에 $Q_j$의 $x$ 좌표와 $y$ 좌표를 나타내는 두 정수가 주어진다. 각 점 $Q_j$가 어느 영역에 속하는지 판정해야 한다. ($|x|,\ |y| \le 10,000$)

출력은 $q$개 줄로 이루어진다. $j$번째 줄에 다음 중 하나를 출력한다.

• $Q_j$가 어떤 영역에도 속하지 않으면 NONE을 출력한다.
• $Q_j$가 정확히 하나의 영역에 속하면 REGION X를 출력한다. $X$는 그 영역의 번호이다.
• $Q_j$가 정확히 두 영역에 속하면 LINE X Y를 출력한다. $X$와 $Y$($X$ < $Y$)는 그 두 영역의 번호이다.
• $Q_j$가 세 개 이상의 영역에 속하면 POINT를 출력한다.