백준 알고리즘 1004번, 어린왕자 (C++)

백준 알고리즘 1004번 어린왕자 스터디 공유 입니다.

 

문제

• 2차원 좌표계에서 출발점과 도착점이 주어진다.
• n개의 원이 주어진다.
• 출발점에서 도착점을 잇는 선 중에서, 원을 통과하는 경우 진입/이탈 한다고 간주한다.
• 진입/이탈한 개수를 센다.
• 참고. 원의 경계가 맞닿거나 서로 교차하는 경우는 없다.
           출발점이나 도착점이 원에 걸친 경우도 없다.

 

문제 해결

• 어려운 문제라고 처음에 생각하였지만, 원이 서로 맞닿거나 교차하는 경우가 없으므로 생각보다 간단하게 생각할 수 있습니다.
• 총 4가지 경우의 수에 대하여 분석이 필요합니다.
• 원의 반지름을 r, 출발점에서 원 사이의 거리를 a, 도착점에서 원 사이의 거리를 b라고 하겠습니다.
• 첫 번째, 출발점과 도착점 모두 원 내부에 있는 경우,
  아래 그림과 같이 진입/이탈 하지 않습니다.
  

  

  백준 알고리즘 1004번, 어린왕자 (C++)

• 두 번째, 출발점과 도착점 모두 원 외부에 있는 경우,
  아래 그림과 같이 진입/이탈하지 않습니다.
  

  

  백준 알고리즘 1004번, 어린왕자 (C++)

• 세 번째, 
  출발점은 원 내부에 있고, 도착점은 원 외부에 있는 경우 1회 이탈 합니다.
  

  

  백준 알고리즘 1004번, 어린왕자 (C++)

• 네 번째,
• 출발점은 원 외부에 있고, 도착점은 원 내부에 있는 경우 1회 진입 합니다.
  

  

  백준 알고리즘 1004번, 어린왕자 (C++)

• 이제, 세 번째와 네 번째 경우에 대하여 count 변수를 증가하도록 소스 코드를 구성하면 됩니다.

 

소스 코드

#include <iostream>

int main() {
	int T = 0;
	int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
	int n = 0;
	int cx = 0, cy = 0, r = 0, r_squared = 0;

	int dist1_squared = 0, dist2_squared = 0;
	
	int cnt;
	std::cin >> T;
	

	for (int i = 0; i < T; i++) {
		std::cin >> x1>> y1 >> x2 >> y2;
		std::cin >> n;
		cnt = 0;

		for (int j = 0; j < n; j++) {
			std::cin >> cx >> cy >> r;
			r_squared = r * r;
			dist1_squared = (cx - x1) * (cx - x1) + (cy - y1) * (cy - y1);
			dist2_squared = (cx - x2) * (cx - x2) + (cy - y2) * (cy - y2);

			if ((dist1_squared > r_squared) && (dist2_squared < r_squared)) cnt++;
			else if ((dist1_squared < r_squared) && (dist2_squared > r_squared)) cnt++;
			else continue;



		}
		std::cout << cnt << std::endl;
	}

	

	return 0;
}