[백준 알고리즘 C/C++] 1004번 문제 풀이 : 어린 왕자

** 이 글을 읽음에 앞서 포스팅 된 소스가 100% 정답은 아님을 밝힙니다.

    더욱 유능한 분께서 클린 / 최적의 소스를 짜셨을 가능성이 높습니다.

    기록용으로 남기며, 참고만 부탁드립니다.

** 백준 알고리즘은 직접 풀이를 해보시는 것을 권장합니다.

---

● 문제

난이도[티어] : 실버 3

백준 알고리즘 1004번 문제 어린 왕자

https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

 

---

● 풀이 방법

여러 원이 그려져 있는 좌표평면에서 출발 지점과 도착 지점을 선을 이을 때, 원(행성계)를 최소 몇 번 접점하는지를 구하는 문제.

 

생각보다 풀이 방법은 단순하다.

각 원(행성계)들에 대해 출발 지점과 도착 지점의 위치적 특성을 생각하면 된다.

위치적 특성은 3가지가 존재한다.

 - CASE 1 : 원(행성계) 내부에 출발 지점과 도착 지점이 위치해 있다.

 - CASE 2 : 원(행성계) 내부에 하나의 출발/도착 지점이 위치해 있고, 다른 지점이 외부에 위치해 있다

 - CASE 3 : 원(행성계) 외부에 출발 지점과 도착 지점이 위치해 있다.

 

우린 CASE 2 의 경우의 원(행성계) 개수를 Count 하면 된다.

---

● 소스 코드

#include <iostream>
#include <math.h>

int main(void)
{
    //1004
    //원의 방정식 (x-x1)^2 + (y-y1)^2 = r^2
    int start_x, start_y;
    int end_x, end_y;
    int test_cnt, ss_cnt;
    int penetration_cnt;
    std::cin >> test_cnt;

    for(int a = 0; a < test_cnt; a++){
        penetration_cnt = 0;
        std::cin >> start_x >> start_y >> end_x >> end_y;
        std::cin >> ss_cnt;
        int ss[ss_cnt][3]; //Stellar system (행성계)
        for(int i = 0; i < ss_cnt; i++){
            int score = 0;
            std::cin >> ss[i][0] >> ss[i][1]>> ss[i][2];

            // 출발 지점이 이 원(행성계) 밖에 존재하는 가?
            if(pow(start_x-ss[i][0],2)+pow(start_y-ss[i][1],2)>pow(ss[i][2],2)){
                score++;
            }

            // 도착 지점이 이 원(행성계) 밖에 존재하는 가?
            if(pow(end_x-ss[i][0],2)+pow(end_y-ss[i][1],2)>pow(ss[i][2],2)){
                score++;
            }

            // 출발/도착 지점 모두 이 원(행성계)밖에 존재하거나 외부에 존재 하지 않는가?
            if(score % 2 != 0){
                penetration_cnt++;
            }
        }
        std::cout << penetration_cnt << std::endl;
    }
}

 

ss(Stellar system) 이중배열을 사용했다.

 - ss[행성계번호(ss_cnt)][원 중심 X좌표(0), 원 중심 Y좌표(1), 반지름(2)]

 

원의 방정식을 사용하여 해당 출발/도착 지점이 해당 원(행성계)에서 밖에 있는지 안에 있는지를 확인했다.

점 (a, b)를 중심으로 하고 반지름이 r인 원의 방정식은 (x - a) ² + (y - b) ²  = r ² 로 나타낼 수 있다.

위 식에서 x와 y에 출발/도착 지점의 값을 대입했을 때, (x - a) ² + (y - b) ²  > r ² 가 성립한다면, 해당 지점이

원 밖에 존재한다는 의미이다.

 

math.h 라이브러리를 통해 사용한 함수

제곱 : pow

#include <math.h>
double pow(double x, double y);

ex) pow(2,10)  : 2의 10승

 

---

● 결과

** 코드 길이가 상이 할 수 있습니다! 그러나 내용물은 같습니다.

    이유)  주석 및 더미 소스 유무