[백준 / JAVA] 백준 알고리즘 1002번 터렛

⏰ 2021-05-21 (금) 12:56:10

screener
시리즈 모아보기
백준 알고리즘

3 / 23

Table of Contents

  • 1. 터렛









터렛

랭크사용 언어
JAVA

🔗 🔗 전체 1002번 문제

조건

시간제한메모리 제한
2초128MB

문제

조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승현의 사진이다.

이석원은 조규현과 백승환에게 상대편 마린(류재영)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.
조규현의 좌표 (x1,y1)(x_1, y_1)와 백승환의 좌표 (x2,y2)(x_2, y_2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1r_1과 백승환이 계산한 류재명과의 거리 r2r_2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
한 줄에 x1x_1, y1y_1, r1r_1, x2x_2, y2y_2, r2r_2가 주어진다. x1x_1, y1y_1, x2x_2, y2y_2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 점수이고, r1r_1, r2r_2는 10,000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

케이스

  • 입력

TC

1
2
3
4
3
0 0 13 40 0 37
0 0 30 0 7 4
1 1 1 1 1 5
  • 출력

TC

1
2
3
2
1
0

풀이

예제의 요소를 사람 이름으로 두었으나, 문제 이해에 방해가 되니 간단하게 서술하면 아래와 같다.
임의의 위치에 있는 점 AA, BB, CC가 존재하며, AACC의 거리, BBCC의 거리가 주어진다.
이 때, CC가 실제로 위치할 수 있는 점의 갯수를 구하는 것. 즉, 간단하게 두 원의 접점을 구하는 문제라고 정의할 수 있다.
원이 완벽하게 겹칠 경우, 그 수가 무수히 많으므로 -1로 표현하라는 조건이 포함된다.

이를 그림으로 표현하면 아래와 같다.

변수는 아래와 같이 정리할 수 있다.

nnxnx_nyny_nrnr_n
1A의 x좌표A의 y좌표A의 반지름
2B의 x좌표B의 y좌표B의 반지름

케이스를 세분화하면 총 6가지로 나눌 수 있다.

  1. 두 원이 정확히 겹칠 경우 (-1)
  2. 두 원이 서로 겹치면서 인접하지 않는 경우 (0)
  3. 두 원이 서로 겹치지 않으면서 인접하지 않는 경우 (0)
  4. 두 원이 서로 겹치면서 인접하는 경우 (1)
  5. 두 원이 서로 겹치지 않으면서 인접하는 경우 (1)
  6. 두 원이 서로 겹치면서 인접하지 않는 경우 (2)

본 풀이에선 x1x_1, y1y_1x2x_2, y2y_2의 거리(distancedistance) 및 r1r_1, r2r_2를 합한 길이(sumsum)와 뺀 길이(subsub)의 절대값을 이용하여 진행한다.

distance=(x1x2)2+(y1y2)2distance = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} sum=r1+r2sum = r_1 + r_2 sub=r1r2sub = \vert r_1 - r_2 \vert
  • case 1 - 두 원이 정확히 겹칠 경우

    두 원의 위치 및 반지름이 서로 동일한 상황.
    distancedistance가 0이며, r1r_1r2r_2의 길이가 동일할 경우 성립한다.

  • case 2 - 두 원이 서로 겹치면서 인접하지 않는 경우

    두 원의 원점과의 거리가 반지름의 차이보다 짧은 상황.
    distance<subdistance < sub일 경우 성립한다.

  • case 3 - 두 원이 서로 겹치지 않으면서 인접하지 않는 경우

    두 원의 원점과의 거리가 반지름의 합보다 긴 상황.
    distance>sumdistance > sum일 경우 성립한다.

  • case 4 - 두 원이 서로 겹치면서 인접하는 경우

    두 원의 원점과의 거리가 반지름의 차이와 일치하는 상황.
    distance==subdistance == sub일 경우 성립한다.

  • case 5 - 두 원이 서로 겹치지 않으면서 인접하는 경우

    두 원의 원점과의 거리가 반지름의 합과 일치하는 상황.
    distance==sumdistance == sum일 경우 성립한다.

  • case 6 - 두 원이 서로 겹치면서 인접하지 않는 경우

    두 원이 서로 적당히 겹치는 상황.
    distance<sumdistance < sum &&\&\& distance>subdistance > sub일 경우 성립한다.

굳이 식으로 표현하지 않아도, 위의 5개 케이스에 부합하지 않는 모든 상황에 적용하면 된다.
위 케이스들을 if문을 사용하여 적절히 표현하면 된다. switch문의 경우 하나의 변수를 기준으로 분기를 판단하므로 해당 알고리즘에 적용하기엔 다소 부적절하다.

전체 소스

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import java.util.Scanner;

/**
 * 백준 전체 1002 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/05/21/a1002">1002 풀이</a>
 * @since 2021.04.21 Wed 21:56:10
 */
public class Main
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 */
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		int length = scanner.nextInt();
		
		for (int i = 0; i < length; i++)
		{
			int x1 = scanner.nextInt();
			int y1 = scanner.nextInt();
			int r1 = scanner.nextInt();
			
			int x2 = scanner.nextInt();
			int y2 = scanner.nextInt();
			int r2 = scanner.nextInt();
			
			System.out.println(calcPoints(x1, y1, r1, x2, y2, r2));
		}
	}
	
	/**
	 * 접점 갯수 반환 함수
	 *
	 * case 1 - 두 원이 정확히 겹칠 경우 (-1)
	 * case 2 - 두 원이 서로 겹치면서 인접하지 않는 경우 (0)
	 * case 3 - 두 원이 서로 겹치지 않으면서 인접하지 않는 경우 (0)
	 * case 4 - 두 원이 서로 겹치면서 인접하는 경우 (1)
	 * case 5 - 두 원이 서로 겹치지 않으면서 인접하는 경우 (1)
	 * case 6 - 두 원이 서로 겹치면서 인접하지 않는 경우 (2)
	 *
	 * @param x1: [int] A의 x좌표
	 * @param y1: [int] A의 y좌표
	 * @param r1: [int] A와 C 사이의 거리
	 * @param x2: [int] B의 x좌표
	 * @param y2: [int] B의 y좌표
	 * @param r2: [int] B와 C 사이의 거리
	 *
	 * @return [int] 접점 갯수
	 */
	private static int calcPoints(int x1, int y1, int r1, int x2, int y2, int r2)
	{
		// 두 점 사이의 거리 계산식
		double distance = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
		
		int sum = r1 + r2;
		int sub = Math.abs(r1 - r2);
		
		// case 1 - 두 원이 정확히 겹칠 경우
		if (distance == 0 && r1 == r2)
		{
			return -1;
		}
		
		// case 2 - 두 원이 서로 겹치면서 인접하지 않는 경우
		else if (distance < sub)
		{
			return 0;
		}
		
		// case 3 - 두 원이 서로 겹치지 않으면서 인접하지 않는 경우
		else if (distance > sum)
		{
			return 0;
		}
		
		// case 4 - 두 원이 서로 겹치면서 인접하는 경우
		else if (distance == sub)
		{
			return 1;
		}
		
		// case 5 - 두 원이 서로 겹치지 않으면서 인접하는 경우
		else if (distance == sum)
		{
			return 1;
		}
		
		// case 6 - 두 원이 서로 겹치면서 인접하지 않는 경우
		else
		{
			return 2;
		}
	}
}

분류

  • 수학
  • 기하학

🏷️ 태그
# 백준
# 알고리즘
# JAVA(자바)
# 기하학
# SILVER
# SILVER IV

읽어주셔서 고마워요!

도움이 되셨다면, 공감이나 댓글을 달아주시는 건 어떤가요?

블로그 운영에 큰 힘이 됩니다.

https://hits.seeyoufarm.com/api/count/incr/badge.svg?count_bg=%23484848&icon=react.svg&icon_color=dodgerblue&title=view&title_bg=%23242424&url=https%3A%2F%2Fblog.itcode.dev%2Fposts%2F2021%2F05%2F21%2Fa1002