2125번: 좀
첫째 줄에 다섯 정수 N, X, Y, U, V가 주어진다. 이는 좀의 현재 위치가 (X, Y)이고, 이동하려는 곳이 (U, V)라는 의미이다. 다음 N개의 줄에는 기워진 부분들을 의미하는 볼록다각형이 주어진다. 각 줄
www.acmicpc.net
kimhwon.tistory.com/27 와 매우 유사한 문제. 다만 원 대신 볼록 다각형이 등장한다.
시점과 종점이 주어지고, 여러 개의 볼록 다각형이 주어진다. 볼록 다각형들의 내부를 지나지 않으면서 종점에 도착하고자 할 때 최단 경로의 길이 (또는 불가능한지)를 구하면 된다. 단, 여기서 볼록 다각형의 내부란 모서리를 포함하지 않는다.
위 문제에서와 같은 전략으로 모든 꼭짓점들과 시점, 종점을 잇는 선분을 모두 만든다. 만든 선분이 모든 볼록 다각형의 외부에 있다면 사용 가능한 선분이다. 사용 가능한 선분으로 이루어진 그래프에서 최단 경로를 구하면 된다.
선분이 볼록 다각형의 내부/외부에 있는지 판정이 매우 까다롭지만, 총 4가지 경우로 분류할 수 있다.
- 선분의 끝점과 다각형의 모서리가 만나는 경우
- 선분의 끝점과 다각형의 꼭짓점이 만나는 경우
- 선분의 중간과 다각형의 꼭짓점이 만나는 경우
- 선분의 중간과 다각형의 모서리가 만나는 경우
네 번째 경우는 선분 교차 판정으로 간단하게 구할 수 있다.(bool intersect(const Line& a, const Line& b)) 만약 교차한다면 선분이 다각형 내부에 있음이 자명하다.
나머지 세 경우는 그림으로 정리했다.
파란 선은 확인하려는 선분, 검은 선은 다각형의 모서리, 초록과 빨간 선은 CCW 상태로 CCW면 초록색, CW면 빨간색이다. 선분 하나에 대하여, 모든 다각형의 모든 모서리를 순회하면서 위의 4가지 조건을 다 확인하면 된다.
코드
논리적으로 이렇게 하면 맞아야 정상이겠지만... 예제 중에 볼록다각형이 아닌 테케가 하나 있다. 게시판에 글을 쓰긴 했으나 아직 반영되진 않았다. 직접 출처인 SEERC 2005에서 데이터를 받아서 확인해보니, 미세하게 안쪽으로 파고든 점이 하나 있는 다각형이 있었다. 이를 예외처리하기 위해, 선분의 중점을 잡고 그 중점이 모든 다각형의 안쪽에 있는지도 판정했다. 수정 요청이 반영되었으며, 재채점까지 완료되었다.
'알고리즘 > BOJ' 카테고리의 다른 글
| 13466번: Endless Turning (0) | 2021.04.17 |
|---|---|
| 15004번: Bearly Made It (4) | 2021.04.15 |