BOJ 2125 - 좀 링크
(2023.06.30 기준 D3)

문제

좀의 현재 위치와 이동하려는 위치, 그리고 N개의 볼록다각형이 주어진다.
좀은 어떠한 볼록다각형 내부로 이동할 수 없고, 볼록다각형의 가장자리로는 이동할 수 있다.
이 때, 목적지까지의 최단 거리 출력

알고리즘

선분 교차 판정과 CCW를 이용하여 그래프에 간선을 추가한 뒤 다익트스라로 최단 거리를 구하자.

풀이

먼저 주어지는 모든 볼록다각형을 CCW를 사용하기 쉽게끔 시계 반대 방향으로 만들자.
그리고 선분 교차 판정에서 문제 조건에 맞게 가장자리를 지나도 교차하지 않는다고 판정하게끔 수정하자. 일직선일 때의 포함, 교차 판정을 지우면 된다.

이제 그래프에 간선을 추가할 차례이다.

위 네 경우에 맞게 모든 점으로 만들 수 있는(시작점과 도착점을 포함한) 선분 쌍을 모든 볼록 다각형마다 검사하여 추가하자.
이런식으로 말이다.

모든 선분 쌍에 대해 검사가 끝나면 다익스트라를 돌리면 된다.

점이 같을 때에 CCW 검사하는 방법은 이 블로그를 참고하였습니다. 감사합니다

코드

D3 이상의 문제는 치팅 방지를 위해 코드를 올리지 않겠습니다.