C++ 어린 왕자 문제 풀기 (백준 1004)

읽어주셔서 감사합니다. 오늘은 백준의 1004번, 터렛 문제에 대해 풀어보도록 하겠습니다.

*이번 문제는 코딩 문제를 빙자한 수학문제입니다. 앞으로 더더욱 이런 유형을 문제가많아질테니 초보자 분들은 참고하세요.

---

code

아래 내용은 수학적인 내용을 다량 함유하고 있습니다. 사실상 수학적인 내용을 제외하면 일반적인 초보자가 짤 수 있는 수준의 코드이지요. 수학적 내용은 아래에서 설명하겠습니다.

#include <iostream>
#include <cmath>

using namespace std;

#define sq(x)	((x)*(x))

int main(void) {
	int T;
	int x1, y1, x2, y2;
	int n;
	int cx, cy, r;
	int count;
	bool A, B;

	cin >> T;
	for (int j = 0; j < T; j++) {
		cin >> x1 >> y1;
		cin >> x2 >> y2;

		count = 0;

		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> cx >> cy >> r;
			A = sq(x1 - cx) + sq(y1 - cy) <= sq(r);
			B = sq(x2 - cx) + sq(y2 - cy) <= sq(r);

			if ((A && !B) || (B && !A)) //A ^ B
				count++;
		}
		cout << count << endl;
	}

	return 0;
}

---

describe

이번 문제는 원의 종류는 나누는 것이 핵심입니다. 다른 여러 방법도 존재하지만, 특히 이해의 간단함을 중점으로 생각하여 고안한 풀이법이라 효율적인 풀이법은 아닐 수 있습니다.

 

1) 추가되는 행성계(원)가 어린왕자, 장미 모두 포함하지 않을때,

항상 행성계(원)을 지나지 않는 경로가 존재한다. 
원의 크기는 한정되어있고 각 원들은 교차되어 있지 않은 상황에서 원 외부→원 외부로의 이동이기 때문.

 

2) 추가되는 행성계(원)가 어린왕자를 포함하지만, 장미는 포함하지 않을때,

항상 행성계(원)을 항상 최소 한 번 지나야 한다.
마찬가지의 상황에서 원 내부→원 외부로의 이동이기 때문.

 

3) 추가되는 행성계(원)가 어린왕자를 포함하지 않지만, 장미는 포함할 때,

항상 행성계(원)을 항상 최소 한 번 지나야 한다.
마찬가지의 상황에서 원 외부→원 내부로의 이동이기 때문.

 

4) 추가되는 행성계(원)가 어린왕자, 장미 모두 포함할 때,

항상 행성계(원)을 항상 최소 한 번 지나야 한다.
마찬가지의 상황에서 원 내부→원 내부로의 이동이기 때문.

 

+ 어떤 점이 원이 포함되는지를 따지는 수식

이를 구현하는 방법은 간단합니다. 원의 중심에서 한 점까지의 거리가, 원의 반지름보다 작으면 점이 원에 포함됩니다. 빈대로 거리가 반지름보다 크면 원에 포함되지 않지요.
문제에서 점이 원의 경계선에 있지는 않는다 했으므로, 거리가 반지름과 같은 경우는 생각하지 않습니다.

---

사용방법

백준 1004번 참고

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

1004번: 어린 왕자

 

---

실행화면

프로그램의 사용 목적을 고려하여 실행화면은 생략하도록 하겠습니다.