[백준 알고리즘] 1004번 어린왕자

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

1004번: 어린 왕자

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어ㄹ진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 (cx, cy, r)이 주어진다. 입력제한은 다음과 같다. (-1000 ≤ x1, y1, x2, y2, cx, cy ≤ 1000, 1 ≤ r ≤ 1000, 1 ≤ n ≤ 50)

좌표와 반지름은 모두 정수이다.

출력

각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.

 

 

풀이

중고등학교 때 배웠던 두 원의 위치관계를 생각해보면 된다.

중심과 중심사이의 거리가 두개의 반지름의 합보다 작거나 클경우 그리고 같은 경우 만나는 점의 갯수가 달라진다.

 

이 문제에서는입력한 행성계의 중점 좌표와 반지름이 주어지고 그 중점 좌표와 출발점, 도착점과의 거리를 생각해본다.

생각해보면 총 세가지 경우의 수가 주어진다.

 

1) 두 점 모두 기준이 되는 행성 밖에 있을 경우에는 전입 / 이탈이 생기지 않는다.

2) 두 점 중 하나의 점만 기준이 되는 행성 안에 있다면 전입 / 이탈이 생긴다.

3) 두 점 모두 기준이 되는 행성 안에 있다면 전입 이탈이 생기지 않는다.

 

기준이 되는 행성 안쪽의 경우의 수만 생각하면 되므로

(x,y)와 각 행성의 중심 (x1,y1) , (x2,y2)와의 거리가 해당 행성의 반지름보다 작으면 된다.

 

#include<stdio.h>
#include<math.h>

using namespace std;

int main() {


	//중심과 중심의 거리가 반지름 보다 작으면 속해 있다는 것이다.

	int term = 0;
	scanf("%d",&term);
	int CirArray[50][3] = { 0 };
	bool BoolOneCir[50] = { false }; // 첫번째 점이 원에 포함되었을 여부의 배열
	bool BoolTwoCir[50] = { false }; // 두번째 점이 원에 포함되었을 여부의 배열
	while (term--) {

		int X1, Y1;
		int X2, Y2;

		scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2); // 점 2개.

		int CirNum = 0;
		scanf("%d", &CirNum);

		for (int i = 0; i < CirNum; i++) {

			int X=0;
			int Y=0;
			int R=0;
			scanf("%d %d %d", &X, &Y, &R);
			BoolOneCir[i] = false;	// 다시초기화
			BoolTwoCir[i] = false; //다시 초기화

			CirArray[i][0] = X;
			CirArray[i][1] = Y;
			CirArray[i][2] = R;

			int X1Length = pow((X - X1), 2);
			int Y1Length = pow((Y - Y1), 2);

			int X2Length = pow((X - X2), 2);
			int Y2Length = pow((Y - Y2), 2);

			int Radious = pow(R, 2);


			if ((X1Length + Y1Length) < Radious) { // 빼는 것 있었음... 까먹..
				BoolOneCir[i] = true;
			}

			if((X2Length + Y2Length) <Radious) {
				BoolTwoCir[i] = true;

			}


		}

		int temp = 0; // 적어도 하나의 원 안에 있을 경우 (하나의 원 안에 있거나 같은 원 안에 있을 경우)
		int temp2 = 0; // 같은 원 안에 있을 경우
		for (int i = 0; i < CirNum; i++) {
			if (BoolOneCir[i] == true || BoolTwoCir[i] == true) {

				temp++;

			}

			if (BoolOneCir[i] == true && BoolTwoCir[i] == true) {

				temp2++;
			}



		}

		int result = abs(temp2 - temp); // 하나의 원에만 점이 있을 경우


		printf("%d\n", result);

	
	}
}

 

temp와 temp2로 나뉘었는데

 

temp는 적어도 하나의 점이 행성 안에 있을 경우이며

temp2는 두개의 점 모두 행성 안에 있을 경우이다. temp2는 전입 / 이탈이 이루어지지 않으므로 temp에서 해당 temp2의 값을 삭제해준다.

 

끝.