★ solved.ac 난이도 : S3
(2021년 12월 29일 기준)
[문제 링크]
1004번: 어린 왕자
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주
www.acmicpc.net
[문제 분석]
원의 성질을 이용한 최적 경로(?) 문제
[풀이]
두 점과 여러 개의 원의 정보가 주어질 때, 교차하는 원의 개수가 가장 적게 되도록 두 점을 잇는 문제라고 생각하시면 됩니다.
(문제에서는 원이 맞닿거나 서로 교차하는 경우는 없고, 시작 및 끝점이 원에 맞닿는 경우는 없습니다.)
먼저, 두 점을 입력 받고, 원의 정보(x 좌표, y 좌표, 반지름)를 입력 받습니다.
원의 정보를 입력 받으면서, 시작점과 끝점에 대해 원 내부에 있는지 검사하고, 이에 대한 결과를 분석하면 됩니다.
(여기에서 교차하는 원의 개수를 cnt라고 하겠습니다.)
경우 1. 두 점이 모두 원 내부에 있는 경우 : 원의 교차 없이 두 점을 이을 수 있습니다. 따라서, cnt를 증가시키지 않습니다.
경우 2. 두 점 중 한 점만 원 내부에 있는 경우 : 이 경우에는 하나의 원을 교차해야 합니다. cnt를 +1 해주시면 됩니다.
경우 3. 두 점 모두 원 외부에 있는 경우 : 원의 바깥 부분을 돌아가서 교차 없이 두 점을 이을 수 있습니다. cnt를 증가시키지 않습니다.
이를 논리식으로 표현해보겠습니다.
(두 점을 각각 A, B라고 하겠습니다. 원 내부에 있을 때 참(true)로 가정하겠습니다.)
if A and B인 경우 : 그냥 무시하시면 됩니다. (경우 1)
else if A or B인 경우 : 경우 2에 해당하는 상황이므로, cnt를 +1 해주시면 됩니다.
경우 3은 구현하지 않으셔도 무방합니다.
[소스 코드]
만약 틀린 부분이 있다면 지적 부탁드릴게요~! (댓글 환영!!)