[백준알고리즘] 1004번: 어린 왕자 -C++

[백준알고리즘] 1004번: 어린 왕자 -C++

1004번: 어린 왕자 (acmicpc.net)

1004번: 어린 왕자

문제에서 서로 다른 두 원이 닿거나 겹칠 수 없다는 조건 덕분에 쉽게 풀 수 있는 문제다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

우선, 각 테스트케이스마다 어린 왕자의 시작 위치와 도착 위치를 받는다. 여기서 움직일 수 있는 방향은 자유자재이기 때문에 실제로 이동하면서 원을 얼마나 지날 수 있는지 세는 것은 불가능하다.

 

따라서 시작 위치에서 도착 위치로 가면서 반드시 지나야하는 원의 개수를 세주는 방법으로 문제를 풀어야 한다.

즉, 다르게 말하면, 시작 위치와 도착 위치를 포함하는 서로 다른 원의 개수를 세면 된다. 시작 위치에서 도착 위치로 이동할 때 도착 위치가 시작 위치는 포함하지 않는 어떠한 원 안에 위치한다고 했을 때, 반드시 이 원을 통과해야하기 때문이다.

 

그리고 원이 서로 겹치거나 맞닿는다고 하지 않았기 때문에, 두 위치가 모두 포함되는 가장 작은 반지름 r을 갖는 원이 있다면, 해당 원의 반지름보다 작은 원에 각자가 포함되는지 알면 된다.

 

사실 여기서 생각해보면, 결국 시작 위치'만' 포함되고 도착 위치는 포함되지 않는 원의 개수와 도착 위치'만' 포함되고 시작 위치는 포함되지 않는 원의 개수를 구해주면, 반드시 진입/탈출하는 원의 개수를 알 수 있다.

 

이러한 사실들이 이해가 안된다면 그림을 그리면 이해가 쉬울 것이다.

혹은 예제 그림만 봐도 이해가 될 수도 있다.

 

예제 그림에서 반드시 진입/탈출이 3번 되는 것은 시작 위치만 포함하는 원의 개수가 1개이고, 도착 위치만 포함하는 원의 개수가 2개이기 때문이다.

---

아래는 통과한 C++ 코드다. 여기서 두 개의 '//' 라인 사이의 내용들은 위에서 말했던 시작 위치'만' 포함하는 원의 개수와 도착 위치'만' 포함하는 원의 개수를 세준다면, 사실 한 번에 구현할 수도 있다. 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	int test_case;
	std::cin >> test_case;
	for (int t = 0; t < test_case; t++)
		solve();
}

double distance(std::pair<int, int> a, std::pair<int, int> b)
{
	return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

void solve(void)
{
	std::pair<int, int> start, end;
	std::cin >> start.first >> start.second >> end.first >> end.second;

	int n;
	std::cin >> n;
	
	std::vector<std::pair<int, std::pair<int, int>>> galaxy(n);
	for (int i = 0; i < n; i++)
	{
		int x, y, r;
		std::cin >> x >> y >> r;
		galaxy[i] = std::make_pair(r, std::make_pair(x, y));
	}
	std::sort(galaxy.begin(), galaxy.end());

	//
	std::vector<bool> start_list(n), end_list(n);
	for (int i = 0; i < n; i++)
	{
		if (distance(start, galaxy[i].second) < galaxy[i].first)
			start_list[i] = true;
		if (distance(end, galaxy[i].second) < galaxy[i].first)
			end_list[i] = true;
	}

	int answer = 0;
	for (int i = 0; i < n; i++)
	{
		if (start_list[i] && end_list[i])
			break;
		if (start_list[i] || end_list[i])
			answer++;
	}
	std::cout << answer << '\n';
	//
}