백준 1004번 : 어린 왕자

문제링크 :https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

 문제설명 

 

1. 어린왕자의 좌표와 꽃의 좌표가 주어지고, 행성의 중심의 좌표와 반지름이 주어진다.

2. 어린왕자가 꽃의 로 가기 위해 거쳐야할 최소 행성의 경계의 수를 구하면된다.

 

 알고리즘 

 

1. 각 행성의 정보를 입력할 때 어린왕자와 꽃이 행성에 속해있는지 여부를 확인한다.

2. 둘다 행성에 속해있거나 아무도 속해있지않다면  이 행성의 경계를 지날필요가없고, 둘중 한명만 속해있다면 이 행성    의 경계를 반드시 지나가야한다.

3. 2번의 과정을 반복하여 행성의 경계를 반드시 지나는 횟수를 출력하면 된다.

 

 코드 

 

#include<iostream>
#include<math.h>
 
using namespace std;
typedef long long ll;
 
pair<int, int> prince, flower;
 
int func(ll y, ll x, ll r) {
    int num = 0;
    
    ll dist = (prince.first - x) * (prince.first - x) + (prince.second - y) * (prince.second - y);
 
    //왕자가 행성내에 속해있을시
    if (dist <= r*r) {
        num++;
    }
 
    
    ll dist2 = (flower.first - x) * (flower.first - x) + (flower.second - y) * (flower.second - y);
 
    //꽃이 같은 행성내에 속해있으시
    if (dist2 <= r*r) {
        num++;
    }
 
    //둘중 하나만 속해있으면 지나야 하는 행성계 하나 추가
    if (num == 1) return 1;
 
    //나머지는 행성계를 지나지 않아도된다.
    else return 0;
}
 
int main() {
 
 
    int a, b, c, d, M, T;
    cin >> T;
 
    for (int i = 0; i < T; i++) {
 
        cin >> a >> b >> c >> d;
        prince = make_pair(a, b);
        flower = make_pair(c, d);
 
        cin >> M;
        int result = 0;
        for (int i = 0; i < M; i++) {
            ll x, y, r;
            cin >> x >> y >> r;
            result += func(y, x, r);
        }
        cout << result << "\n";
    }
}