백준 1004번: 어린 왕자 (C++)

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

1004번: 어린 왕자

---

Level: Silver III

Solved By: Geometry

 

$$ (x-a)^2 + (y-b)^2 = r^2 \; (a, b = Center\;points)$$

원의 방정식을 이용해 풀었습니다.

x와 y에 값을 대입했을 때 r^2보다 작으면 내부, 크면 외부인 점을 활용합니다. (겹치는 점은 안 주어진다 함)

시작점과 도착점 둘 다 내부에 있는 경우와 외부에 있는 경우는 안 지나쳐도 되기 때문에 제외됩니다.

즉, 한 점이 내부, 한 점이 외부라면 무조건 지나쳐야 하므로 이러한 점을 활용하여 풀 수 있었습니다.

#include <iostream>
using namespace std;

int T;
int x1, y1, x2, y2;
int N;

// 내부에 있으면 True
bool solve(int a, int b, int c, int d, int e){
    int comp = c * c;
    int X = (a - d) * (a - d);
    int Y = (b - e) * (b - e);
    if(X + Y < comp) return true;
    else return false;
}

int main(){
    cin >> T;
    for(int t = 1; t <= T; t++){
        cin >> x1 >> y1 >> x2 >> y2;
        int res = 0;
        cin >> N;
        for(int i = 0; i < N; i++){
            int a, b, c; cin >> a >> b >> c;
            bool f1 = solve(a, b, c, x1, y1);
            bool f2 = solve(a, b, c, x2, y2);
            
            if((f1 && !f2) || (!f1 && f2)) res++;
        }
        cout << res << '\n';
    }
    
    return 0;
}