Baekjoon - 어린왕자

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

 

GPT한테 물어보니 DFS/BFS로 어렵게 풀더라 그래서 나는 그냥 단순 구현으로 풀 수 있겠다 생각해서 그렇게 풀었다.

 

출발점과 도착점 사이에 몇 번의 행성계를 진입하고 이탈해야 하는지 구하는 문제다. 각 행성계는 원으로 주어지며, 두 점이 원의 내부에 있는지 여부를 확인하여 진입/이탈 횟수를 계산할 수 있따.

 

Algorithm

1. 각 행성계에 대해 출발점과 도착점이 그 행성계를 포함하는지 여부를 확인합니다.
2. 출발점과 도착점이 같은 행성계에 대해 포함되거나 포함되지 않는지 여부를 체크합니다.
3. 출발점과 도착점의 상태가 다르면 진입/이탈이 발생한다고 판단하고, 그 횟수를 계산합니다.

 

Code

#include <iostream>
#include<cmath>

using namespace std;

bool distance(int a, int b, int c, int d, int r) {
	return (pow(a - c, 2) + pow(b - d, 2)) < pow(r, 2);
}

int main()
{
	int t;
	int cnt = 0;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		int n;
		cin >> n;
		for (int j = 0; j < n; j++) {
			int cx, cy, cr;
			cin >> cx >> cy >> cr;

			bool start = distance(x1, y1, cx, cy, cr);
			bool end = distance(x2, y2, cx, cy, cr);

			if (start != end) {
				cnt++;
			}
		}
		cout << cnt << "\n";
		cnt = 0;
	}
	return 0;
}

 

 

Desciption

// 두 점 (a, b)가 원 (cx, cy, r) 내부에 있는지 확인하는 함수
bool distance(int a, int b, int cx, int cy, int r) {

• distance 함수는 주어진 점 (a, b)가 원 (cx, cy)의 반지름 r 안에 있는지 확인하는 함수이다.
• 함수의 매개변수는 a, b (점의 좌표), cx, cy (원의 중심 좌표), r (원의 반지름).
• 반환값은 bool 타입으로, 점이 원 내부에 있으면 true, 아니면 false를 반환한다.

    return (pow(a - cx, 2) + pow(b - cy, 2)) < pow(r, 2);
}

• pow(a - cx, 2)는 점 (a, b)와 원의 중심 (cx, cy) 간의 x좌표 차이의 제곱을 계산한다.
• pow(b - cy, 2)는 y좌표 차이의 제곱을 계산한다.
• 이 두 값의 합은 점 (a, b)와 원의 중심 (cx, cy) 간의 거리 제곱을 나타낸다.
• pow(r, 2)는 원의 반지름 r의 제곱이다.
• 점이 원의 내부에 있을 경우, 두 점 간의 거리 제곱이 원의 반지름 제곱보다 작을 것이다. 그래서 그 조건을 만족하면 true를 반환하고, 그렇지 않으면 false를 반환한다.