[C++] 백준/Silver/1004. 어린 왕자

문제 링크 (백준 1004번)

문제 분석

어린 왕자가 출발점에서 도착점까지 이동하면서 거쳐야 하는 최소한의 행성계 진입/이탈 횟수를 구하는 문제다.
행성계는 원으로 표현되며, 출발점과 도착점, 그리고 행성계의 중심과 반지름이 주어진다.
문제의 조건에 따라 행성계 경계는 서로 교차하거나 맞닿지 않고, 출발점과 도착점이 경계에 걸쳐지는 경우도 없다.

문제 로직

1. 행성계 내부 판정
   • 두 점 사이의 거리를 계산해서 해당 점이 행성계 내부에 있는지 확인
2. 진입/이탈 횟수 계산
   • 출발점과 도착점이 특정 행성계 내부/외부에 속하는 관계가 다를 때만 진입/이탈 횟수를 증가시킨다.
   • 이 과정을 통해 최소 진입/이탈 횟수를 구한다.
3. 전체 흐름
   • 각 테스트 케이스마다 모든 행성계를 검사하면서 위 조건을 만족하는 경우를 카운트한다.

거리 계산

float Distance(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

두 점 사이의 유클리드 거리를 계산하는 함수.

 

행성계 내부 판정

bool InCircle(int x1, int y1, int x2, int y2, int r) {
    return Distance(x1, y1, x2, y2) <= r;
}

점이 행성계 내부에 있는지 확인하는 함수.

 

진입/이탈 계산

while (n--) {
    cin >> cx >> cy >> r;
    answer += InCircle(cx, cy, x1, y1, r) != InCircle(cx, cy, x2, y2, r);
}

출발점과 도착점이 행성계 내부/외부에 속하는 상태가 다른 경우에만 진입/이탈 횟수를 증가시킨다.