| 문제
조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다.
이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.
조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.
| 입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
한 줄에 x1, y1, r1, x2, y2, r2가 주어진다. x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다.
| 출력
각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.
| 예제 입력 1
3
0 0 13 40 0 37
0 0 3 0 7 4
1 1 1 1 1 5
| 예제 출력 1
2
1
0
| 문제의 키 포인트
1. 조규현의 좌표(x1, y1)와 백승환의 좌표(x2, y2), 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표수란?
> 글만으로는 이것이 류재명의 위치가 조규현과 백승환이 탐지한 범위에서 겹치는 지점만을 말하는 것인지, 각각 탐지한 범위 전체를 말하는 것인지 파악이 어렵다.
> 주어진 예제 입/출력을 그려봄으로써 문제에서 요구하는 값을 확인할 수 있었다.
> 예제 입력 1에서 두번째 줄에 주어진 0 0 13 40 0 37을 그래프상에 도식해보면 위와 같았다. 이에 대한 출력으로는 2가 나온다고 하였으므로, 문제에서 요구하는 것은 둘이 탐지한 범위에서 정확히 겹치는 부분의 갯수를 말하는 것이라는 걸 알 수 있었다.
> 하나의 예시로만 판단하는 것은 섯부른 판단일 수 있으므로, 나머지 두 예제 모두 그려보았다. 결과적으로, 앞서 판단한 바와 같이 문제에서 요구하는 것은 조규현과 백승현이 탐지한 범위에서 류재명이 위치가 겹치는 곳을 출력하라는 것임을 알 수 있었다.
2. 위 그래프를 수학적으로 표현해보자.
> 기본적으로, 중심점이 (x1, y1) 그리고 반지름 r1의 원의 방정식 공식은 (x-x1)2 + (y-y1)2=r12
3. 결론
> 조규현의 원의 방정식: (x-x1)2 + (y-y1)2 = r12
> 백승환의 원의 방정식: (x-x2)2 + (y-y2)2 = r22
> 이 둘의 교차점의 갯수를 계산하여 출력하면 된다.
4. 위의 결론의 경우 다른 경우의 수를 고려하지 못하여, 제대로된 답을 도출하기 어려웠다.
원의 접하는 경우의 수를 조금 더 구글링해보니 아래와 같은 경우들을 고려해주면 된다고 한다.
여기서 두 원의 반지름 r1, r2(r1 <= r2)라 하고, 중점 사이의 거리를 d라고 한다.
(1) 원이 두 점에서 만나는 경우
> r2 - r1 < d < r1 + r2
(2) 두 원이 외접하는 경우 (한 점에서 만나는 경우)
> d = r1 + r2
(3) 두 원이 내접하는 경우 (한 점에서 만나는 경우)
> d = r2 - r2
> d != 0
(4) 하나의 원이 다른 원을 포함하는 경우 (어떠한 점에서도 만나지 않는 경우)
> d < r2 - r1
(5) 두 원이 멀리 떨어져 만나지 않는 경우
> d > r1 + r2
(6) 두 원이 일치하는 경우 (무수히 많은 점에서 만나는 경우)
> d = 0, r1= r2
| 해결방안(Solution)
1. 최종적으로 도출한 각각의 경우의 수에 맞추어 코드를 작성한다.
2. 이 때 거리를 구할 때 제곱과 제곱근을 구하는 경우가 있으므로, 이 때는 math 라이브러리를 추가하여 작성하도록 한다.
| 소스코드(SourceCode)
// BOJ_1002_Turret, 터렛
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int main(void)
{
int d, dx, dy, x1, x2, y1, y2, r1, r2;
int i, T, temp, add, sub;
scanf("%d", &T);
for (i = 0; i < T; i++)
{
scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2);
dx = x1 - x2;
dy = y1 - y2;
// r1, r2, swap() 판단
if (r1 > r2)
{
temp = r1;
r1 = r2;
r2 = temp;
}
// 비교값 계산
add = r1 + r2;
add = pow(add, 2);
sub = r2 - r1;
sub = pow(sub, 2);
d = pow(dx, 2) + pow(dy, 2);
// 조건 판단 후 출력
if (d < add && d > sub)
{
printf("2");
}
else if (d == add || (d == sub && d != 0))
{
printf("1");
}
else if (d < sub || d > add)
{
printf("0");
}
else if (d == 0)
{
if (r1 == r2)
{
printf("-1");
}
else
{
printf("0");
}
}
printf("\n");
}
return 0;
}처음에는 두 반지름의 합과 차를 거리와 비교시 sqrt() 함수를 활용하여 직접적인 거리값을 비교하려고 하였었습니다. 그런데, 이 경우 거리의 제곱값에서 sqrt() 함수로 제곱근을 구하는 과정에서 오차가 발생하였고, 이로 인해 제출시 틀렸습니다. 라는 결과가 돌아왔습니다. 이를 해결하고자, 합과 차의 값을 제곱하여 거리의 제곱값과 비교하는 형태로 진행하였고 결과적으로 문제를 맞출 수 있었습니다.
그럼 오늘도 즐거운 코딩!!
| 문제출처
https://www.acmicpc.net/problem/1002
1002번: 터렛
각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.
www.acmicpc.net
| 추가적으로 이용한 웹페이지
사분면에 그래프 작성: https://www.desmos.com/calculator?lang=ko
Desmos | 그래핑 계산기
www.desmos.com
'코딩 | 알고리즘 & 문제풀이 > 백준_Backjoon' 카테고리의 다른 글
| [C언어] Backjoon_Code 10870, 피보나치 수 (0) | 2021.08.04 |
|---|---|
| [C언어] Backjoon_Code 10872, 팩토리얼 (0) | 2021.08.03 |
| [C언어] Backjoon_Code 3053, 택시 기하학 (0) | 2021.08.01 |
| [C언어] Backjoon_Code 4153, 직각삼각형 (0) | 2021.07.31 |
| [C언어] Backjoon_Code 3009, 네 번째 점 (0) | 2021.07.30 |
