민코프스키 합 영역 질의
다이아몬드 III의견: 0
두 볼록 다각형 \(A\)와 \(B\)가 주어진다. \(A\)는 \(N\)개, \(B\)는 \(M\)개의 꼭짓점을 가지며, 두 다각형 모두 꼭짓점이 반시계 방향으로 주어지고 세 점이 한 직선 위에 있지 않은 엄격한 볼록 다각형이다.
민코프스키 합 \(A \oplus B = \{\, \mathbf{a} + \mathbf{b} \mid \mathbf{a} \in A,\ \mathbf{b} \in B \,\}\)를 생각하자. 여기서 \(A\), \(B\)는 경계뿐 아니라 내부를 포함한 닫힌 영역이다.
이후 \(Q\)개의 질의 점 \(\mathbf{p}\)가 주어진다. 각 질의에 대해 \(\mathbf{p}\)가 \(A \oplus B\)에 속하는지(경계 포함) 판별하여, 속하면 \(1\), 아니면 \(0\)을 출력하여라.
\(3 \le N, M \le 100{,}000\)
\(1 \le Q \le 200{,}000\)
모든 좌표의 절댓값은 \(10^8\) 이하의 정수이다.
\(A\), \(B\)는 각각 엄격한 볼록 다각형이며 꼭짓점이 반시계 방향으로 주어진다.
첫 줄에 \(A\)의 꼭짓점 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 \(A\)의 꼭짓점이 반시계 방향으로 \(x_i\), \(y_i\)로 주어진다.
그 다음 줄에 \(B\)의 꼭짓점 수 \(M\)이 주어지고, 이어 \(M\)개의 줄에 \(B\)의 꼭짓점이 반시계 방향으로 주어진다.
그 다음 줄에 질의 수 \(Q\)가 주어지고, 이어 \(Q\)개의 줄에 질의 점 \(x\), \(y\)가 주어진다.
각 질의에 대해 점이 \(A \oplus B\)에 속하면 \(1\), 아니면 \(0\)을 한 줄에 하나씩 출력한다.
4
0 0
1 0
1 1
0 1
4
0 0
1 0
1 1
0 1
4
1 1
2 2
3 0
0 0
1
1
0
1두 단위 정사각형의 민코프스키 합은 꼭짓점 \((0,0),(2,0),(2,2),(0,2)\)인 \(2\times2\) 정사각형이다. \((1,1)\)은 내부, \((2,2)\)는 꼭짓점(경계), \((3,0)\)은 바깥, \((0,0)\)은 꼭짓점이므로 결과는 \(1,1,0,1\)이다.
3
0 0
2 0
0 2
3
0 0
1 0
0 1
4
1 1
3 0
0 3
2 1
1
1
1
1합 다각형은 꼭짓점 \((0,0),(3,0),(0,3)\)인 삼각형이다. \((1,1)\)은 내부, \((3,0)\)과 \((0,3)\)은 꼭짓점(경계), \((2,1)\)은 빗변 위(경계)이므로 모두 \(1\)이다.
riseoj 작성
출처 Original
평가 및 의견
민코프스키 합 영역 질의
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
민코프스키 합 영역 질의