BOJ - 1004 어린 왕자 해결 전략 (C++)

• 문제 링크
  백준 1004번 - 어린 왕자

해결 전략

  문제를 읽다 보면, 문제의 조건(ex. 경계가 맞닿거나 ~)이 아래와 같은 아이디어를 유도하고 있음을 금새 알아챌 수 있다.

출발지와 도착지를 포함하지 않는 원들은 모두 삭제해도 상관 없다.

즉, 각 행성과 출발지/도착지 간의 거리를 이용해 포함 여부를 확인하고, 포함 시, 해당 행성을 Mark하는 식으로 해결할 수 있을 것이다.

~> 위의 아이디어를 토대로 어렵지 않게 해결책을 설계할 수 있다. 허나, 본인은 이 문제에 대해 한 차례 '틀렸습니다."를 받았는데, 그 이유는 다음과 같은 사실을 간과해서였다.

이때, 출발지와 도착지를 모두 포함한 행성의 경우, 그 행성에 대해선 삭제해야 한다.

~> 조금만 생각해보면 당연하다는 것을 알 수 있다. 이렇게 해서 본 문제를 해결할 수 있다.

  아래는 정답 코드이다.

#include <iostream>
#include <math.h>
// BOJ 1004 - Young Princess
#define DONT_BLANK 1
#define CAN_BLANK  0
using namespace std;

double planet[51][4];

double dist(double x1, double y1, double x2, double y2)
{ return sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2)); }

int main(void) {
	int t, n, blanked;
	double x1, y1, x2, y2, cx, cy, r;

	cin >> t;
	while (t--) {
		cin >> x1 >> y1 >> x2 >> y2 >> n;  blanked = 0;

		for (int i = 1; i <= n; i++) {
			cin >> cx >> cy >> r;
			planet[i][0] = cx;  planet[i][1] = cy;  planet[i][2] = r;

			if (dist(cx, cy, x1, y1) < r || dist(cx, cy, x2, y2) < r) {
				planet[i][3] = DONT_BLANK;
				if (dist(cx, cy, x1, y1) < r && dist(cx, cy, x2, y2) < r)
					planet[i][3] = CAN_BLANK;
			}
			else planet[i][3] = CAN_BLANK;
		}

		for (int i = 1; i <= n; i++) {
			if (planet[i][3] == DONT_BLANK) continue;
			
			if (dist(planet[i][0], planet[i][1], 0, 0) + planet[i][2] < 5000)
				blanked++;
		}

		cout << (n - blanked) << '\n';
	}

	return 0;
}