문제 67
볼록 다각형 내부의 점 판정
$N$개의 꼭짓점으로 이루어진 볼록 다각형이 있다. $Q$개의 점에 대해 각 점이 볼록 다각형의 내부에 있는지 판별하라.
경계 위에 있는 점은 내부에 있는 것으로 보지 않는다.
입력
첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(3 \le N \le 200\,000; 1 \le Q \le 200\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 볼록 다각형의 꼭짓점 좌표를 의미하는 두 정수 $x$, $y$가 공백으로 구분되어 주어진다. $(-10^9 \le x, y \le 10^9)$
꼭짓점은 반시계 방향 순서로 주어진다.
그다음 줄부터 $Q$개의 줄에 걸쳐 판별할 점의 좌표를 의미하는 두 정수 $x$, $y$가 공백으로 구분되어 주어진다. $(-10^9 \le x, y \le 10^9)$
주어지는 다각형의 넓이는 양수이다.
출력
각 점마다 볼록 다각형의 내부에 있으면 Yes를, 그렇지 않다면 No를 한 줄에 하나씩 출력한다.
예제 입력 1
4 5 0 0 4 0 4 4 0 4 2 2 4 2 5 5 0 0 -1 2
예제 출력 1
Yes No No No No
공식 해설
꼭짓점 하나에서 부채꼴로 나누기
반시계 방향 꼭짓점을 $P_0,P_1,\cdots,P_{N-1}$이라 하자. $P_0$와 나머지 꼭짓점을 이으면 볼록 다각형이 삼각형들로 나뉜다. 질의점 $X$가 들어갈 방향 구간을 이분 탐색하면 모든 변을 검사할 필요가 없다.
$\operatorname{ccw}(A,B,C)$는 벡터 $B-A$, $C-A$의 외적을 나타낸다. 이 값이 양수이면 $A$에서 $B$로 향하는 직선의 왼쪽에 $C$가 있다.
먼저
\[
\operatorname{ccw}(P_0,P_1,X)>0,\qquad
\operatorname{ccw}(P_0,P_{N-1},X)<0
\]
인지 확인한다. 하나라도 아니면 바깥이거나 실제 다각형 경계 위이므로 No이다.
방향을 이분 탐색하기
남은 경우에는 $\operatorname{ccw}(P_0,P_i,X)\ge0$인 가장 큰 $i$를 찾는다. 꼭짓점의 방향이 순서대로 주어지고 다각형이 볼록하므로 이 조건은 이분 탐색할 수 있다. 앞의 검사에 의해 $1\le i\le N-2$이다.
$X$는 $P_0P_i$와 $P_0P_{i+1}$의 방향 사이에 있으므로 마지막으로 실제 변 $P_iP_{i+1}$에 대해
\[
\operatorname{ccw}(P_i,P_{i+1},X)>0
\]
인지 확인한다. 참이면 내부이고, 아니면 경계 또는 바깥이다.
이분 탐색에서는 등호를 허용해야 내부 대각선 위의 점도 포함된다. 실제 다각형 변을 검사할 때만 엄격한 부등식을 사용한다.
시간복잡도는 $O(N+Q\log N)$, 공간복잡도는 $O(N)$이다. 외적은 정수로 계산하여 경계의 등호를 정확히 판정한다.
구현 · 언어별 풀이
C++ 구현
꼭짓점은 주어진 순서대로 저장하며 다시 정렬하지 않는다. 외적은 long long으로 계산한다. 이분 탐색의 방향 비교에는 등호를 포함하지만, 실제 다각형 변의 내부 판정에는 엄격한 부등식을 사용해야 한다.
C 구현
주어진 반시계 순서를 그대로 유지한다. 첫 꼭짓점 기준 외적과 부채꼴 이분 탐색을 long long으로 계산한다. 실제 다각형 변 위는 제외하지만 내부 대각선의 외적이 $0$이라는 이유로 경계라고 단정하지 않는다.
Python 구현
정점 순서를 다시 sort하지 않는다. int 외적으로 부채꼴을 이분 탐색하고 마지막 실제 변에 대해 엄격한 내부 여부를 검사한다. 내부 대각선과 외부 경계를 구분한다.
Java 구현
long 좌표와 외적으로 정수 판정을 한다. 첫 꼭짓점의 양쪽 경계 검사와 부채꼴 이분 탐색을 분리한다. 내부 대각선 위 점을 무조건 제외하는 구현을 피한다.
Rust 구현
i64 CCW와 usize 구간 인덱스로 부채꼴을 이분 탐색한다. 입력의 CCW 순서를 유지하며 마지막 삼각형의 실제 다각형 변에서는 엄격한 부호를 검사한다.
JavaScript 구현
반시계 방향으로 주어진 꼭짓점 순서를 그대로 사용한다.
외적은 좌표 차를 BigInt로 변환한 뒤 계산하고 0n과 비교한다. 공통 풀이처럼 실제 경계 검사에서는 엄격한 부등식을, 내부 대각선의 이분 탐색에서는 등호를 사용한다.
입력 다각형에는 일직선 위 꼭짓점이 있을 수 있으며, 기준점과 같은 반직선에 있는 바깥 경계도 내부에서 제외한다.