백준 : 1002번, 터렛

문제 주소 : www.acmicpc.net/problem/1002

정답 비율 : 20.177% (2020.11.11 22:32 기준)

1002번: 터렛

문제 난이도에 비해 정답률이 낮아서 살짝 "뭐지?" 하는 느낌이 들었지만 풀면서 이유를 알게 되었습니다.

 

개인적인 생각으로 너무 쉬워서 머리로만 생각하고 풀이를 작성하고 제출했기 때문이라고 생각합니다. (저 같은 경우에도 실패하면 또 무슨 경우가 있지 하고 생각하고 수정하고 그렇게 5번 실패하고 나서야 조용히 공책이랑 펜을 가져와 모든 경우의 수에 대하여 천천히 정리하였습니다. ㅎㅎ)

 

문제 간단 요약 : 두 개의 원의 중심을 주어지고 각 원의 반지름 값을 전달해줍니다. 그러곤 두 원의 교점의 개수를 리턴하는 문제입니다.

 

 

모든 경우의 수 

 

정의 

r_1 : 빨간색 원의 반지름

r_2 : 파란색 원의 반지름

항상 r_1 < r_2라고 가정합니다.

len : 두원 사이의 거리

 

1) 한 점에서 만나는 경우

 

- 원이 외접하는 경우 : len = r_1 + r_2

양변 제곱 : len^2 = r_1^2 + r_2^2 + 2 * r_1 * r_2

 

- 원이 내접하는 경우 : len = r_2 - r_1

양변 제곱 : len^2 = r_1^2 + r_2^2 - 2 * r_1 * r_2

 

2) 만나지 않는 경우

 

- 두 원이 멀리 떨어져 있는 경우 : len > r_1 + r_2

양변 제곱 : len^2 > r_1^2 + r_2^2 + 2 * r_1 * r_2

 

- 하나의 원이 다른 원을 포함하는 경우

1. 두 개의 원점이 다를 경우 : len + r_1 < r_2     =>     len < r_2 - r_1
   양변 제곱 : len^2 < r_1^2 + r_2^2 - 2 * r_1 * r_2
2. 두 개의 원이 같을 경우 : len = 0 and r_2 != r_1

3) 무한대로 만나는 경우

 

- 두 원이 일치하는 경우 : len = 0 and r_2 = r_1

 

4) 두 점에서 만나는 경우

 

- 반지름의 합이 내접과 외접 사이에 있을 경우 : r_2 - r_1 < len < r_2 + r_1

양변 제곱 :  r_1^2 + r_2^2 - 2 * r_1 * r_2 < len^2 < r_1^2 + r_2^2 + 2 * r_1 * r_2

 

 

이때 len^2 - r_1^2 - r_2^2 = k로 치환하고 k에 절댓값을 씌우면 각 경우에 대하여 다음이 성립합니다.

 

1) 두 점에서 만나는 경우 : abs(k) < 2 * r_1 * r_2

2) 한 점에서 만나는 경우 : abs(k) = 2 * r_1 * r_2

3) 만나지 않는 경우의 수 : abs(k) > 2 * r_1 * r_2 // d = 0 and r_1 != r_2

4) 무한대로 만나는 경우 : d = 0 and r_1 = r_2

 

#include<stdio.h>

int main()
{
	int testcase = -1, i = -1;

	scanf("%d", &testcase);

	for (i = 0; i < testcase; i++)
	{
		int x1 = -1, y1 = -1, r1 = -1;
		int x2 = -1, y2 = -1, r2 = -1;
		int LenSquared = -1;

		scanf("%d %d %d", &x1, &y1, &r1);
		scanf("%d %d %d", &x2, &y2, &r2);

		LenSquared = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);

		if (LenSquared == 0)
		{
			if (r1 == r2)
				printf("-1\n");
			else
				printf("0\n");
		}
		else
		{
			int tmp = LenSquared - r1 * r1 - r2 * r2;
			tmp = tmp < 0 ? tmp * -1 : tmp;

			if (tmp < 2 * r1 * r2)
				printf("2\n");
			else if (tmp == 2 * r1 * r2)
				printf("1\n");
			else
				printf("0\n");
		}
	}
}

 

여담으로 tmp == 2 * r1 * r2를 tmp = 2 * r1 * r2로 써서 10분도 헤매었습니다. ㅠㅠ