백준 1004번) 어린 왕자

본문의 코드보다 더 효율적인 코드가 분명 존재합니다.

참고만 해주시면 감사하겠습니다.

코드 지적은 언제나 환영입니다.

---

풀이

출발, 목적 지점의 좌표가 주어지고

행성의 갯수, 각 행성의 좌표 및 반지름이 입력된다.

출발 지점에서 목표 지점까지 이동할 때 지나치는 행성의 경계면의 수를 구한다.

 

vector(가변배열)에 pair를 이용하여 pair(반지름, pair(행성좌표_x, 행성좌표_y))를 저장한다.

출발 지점과 각 행성과의 거리를 구하고 계산된 거리가 각 행성의 반지름보다 작다면 해당 행성의 범위내에 포함된 것이다.

행성의 범위내에 포함되어 있다는 것은 목적지점으로 이동할 때 반드시 경계면을 거쳐야 한다는 의미이므로 카운트변수를 증가시킨다.

 

목적지점의 경우에도 위와 동일하게 카운트한다.

 

하지만, 같은 행성 범위내에 출발 지점과 목적 지점이 있는 경우에는 경계면을 거칠 필요가 없기때문에 같은 범위내에 속해있는 케이스의 수를 구하고 x2를 하여 빼준다.

 

코드

#include "iostream"
#include "vector"
#include "cmath"

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tc;
    cin >> tc;

    for(int i = 0 ; i < tc ; i++){
        int start_x, start_y, end_x, end_y;
        cin >> start_x >> start_y >> end_x >> end_y;

        int count_planet;
        cin >> count_planet;

        vector<pair<int, pair<int, int>>> planet_list;
        for(int j = 0 ; j < count_planet ; j++){
            int tmp_x, tmp_y, tmp_r;
            cin >> tmp_x >> tmp_y >> tmp_r;
            planet_list.push_back(make_pair(tmp_r, make_pair(tmp_x, tmp_y)));
        }

        // 1. 출발지점과 각 행성들과의 거리를 구하고 거리가 각 행성의 반지름보다 작을 때 해당 행성안에 위치한 것으로 간주한다.
        int cnt = 0;
        for(int j = 0 ; j < count_planet ; j++){
            double distance = sqrt(pow((start_x-planet_list[j].second.first),2)+pow((start_y-planet_list[j].second.second),2));
            if(distance < planet_list[j].first){
                cnt++;
            }
        }

        // 2. 목적지점과 각 행성들과의 거리를 구하고 거리가 각 행성의 반지름보다 작을 때 해당 행성안에 위치한 것으로 간주한다.
        int cnt2 = 0;
        for(int j = 0 ; j < count_planet ; j++){
            double distance = sqrt(pow((end_x-planet_list[j].second.first),2)+pow((end_y-planet_list[j].second.second),2));
            if(distance < planet_list[j].first){
                cnt2++;
            }
        }

        // 3. 출발지점과 목적지점이 같은 행성안에 있는 경우 카운트
        int cnt3 = 0;
        for(int j = 0 ; j < count_planet ; j++){
            double distance = sqrt(pow((start_x-planet_list[j].second.first),2)+pow((start_y-planet_list[j].second.second),2));
            double distance2 = sqrt(pow((end_x-planet_list[j].second.first),2)+pow((end_y-planet_list[j].second.second),2));
            if(distance < planet_list[j].first && distance2 < planet_list[j].first){
                cnt3++;
            }
        }

        cout << cnt+cnt2-(cnt3*2) << '\n';
    }

    return 0;
}