별자리 순찰
골드 V의견: 0
왕국의 밤하늘에는 \(N\)개의 별이 볼록 다각형을 이루며 별자리를 형성하고 있다. 별들의 좌표는 반시계 방향(CCW) 순서로 주어진다.
순찰대원이 \(Q\)번 보고를 보내 온다. 각 보고에는 좌표 \((p_x, p_y)\)가 포함되어 있으며, 이 좌표가 별자리(볼록 다각형의 내부 또는 경계) 안에 있는지 판별해야 한다.
- \(1 \le N \le 100\,000\)
- \(1 \le Q \le 200\,000\)
- 모든 좌표의 절댓값은 \(10^8\) 이하인 정수이다.
- 입력된 볼록 다각형은 반시계 방향 순서로 주어지며, 볼록성이 보장된다.
- \(N = 1\)이면 '점', \(N = 2\)이면 '선분'으로 간주한다.
첫째 줄에 꼭짓점의 수 \(N\)과 질의의 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 볼록 다각형의 꼭짓점 좌표 \((x_i, y_i)\)가 반시계 방향 순서로 주어진다.
다음 \(Q\)개의 줄에 질의 좌표 \((p_x, p_y)\)가 주어진다.
\(Q\)개의 줄에 걸쳐 각 질의 좌표가 볼록 다각형의 내부 또는 경계 위에 있으면 YES, 외부에 있으면 NO를 출력한다.
4 5
0 0
4 0
4 4
0 4
2 2
0 0
5 3
4 2
2 4
YES
YES
NO
YES
YES
정사각형 꼭짓점은 \((0,0),(4,0),(4,4),(0,4)\)이다. \((2,2)\)는 내부, \((0,0)\)은 꼭짓점(경계 포함), \((5,3)\)은 외부, \((4,2)\)는 변 위, \((2,4)\)는 변 위이므로 YES YES NO YES YES를 출력한다.
3 4
0 0
6 0
3 5
3 1
6 1
0 0
3 5
YES
NO
YES
YES
삼각형 \((0,0),(6,0),(3,5)\)에서 \((3,1)\)은 내부(YES), \((6,1)\)은 외부(NO), \((0,0)\)은 꼭짓점(YES), \((3,5)\)은 꼭짓점(YES)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
별자리 순찰
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
별자리 순찰