[JAVA/백준] 1002번 문제 해설 및 답안

안녕하세요, 하루플입니다.

 

오늘은 백준 JAVA 1002번 문제를 풀이해보겠습니다.

 

문제

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

조규현과 백승환

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.

조규현의 좌표 (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보다 작거나 같은 자연수이다.

 

 

---

이게 무슨 문제지... 했는데 하나식 이해하니 풀어졌다..

먼저 내용을 깔끔하게 정리했다.

조규현 좌표(x1, y1)   -> 류재명까지 거리 r1 백승환 좌표(x2, y2)   -> 류재명까지 거리 r2 이후 x1, y1, r1, x2, y2, r2 입력이 주어졌을 때 류재명이 있을 수 있는 위치의 수는?

글로는 어려우니 그림을 그려 생각해보자.

 

 

1. 두 원이 완전히 겹치는 경우 (접점의 개수가 무한할 때)

이런 경우 두 원의 중심이 같고 반지름도 같다. 

x1 = x2

y1 = y2

r1 = r2

로 두 원은 완전히 동일하다

 

 

2. 접점이 없을 때

- 두 점 사이의 거리가 각 원의 반지름 합보다 클 때

(𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )/2  > 𝑟₁ + 𝑟₂

를 풀면 (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  > (𝑟₁ + 𝑟₂)²

 

 

 

- 한 원 안에 다른 원이 있으면서 접점이 없을 때

두 원의 반지름 차가 두 원간의 중점 거리보다 크면 접점을 갖지 않게 된다.

(𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  <  ∣𝑟₂ - 𝑟₁∣

를 풀면  (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  <  (𝑟₂ - 𝑟₁)² 

 

 

 

 

3. 접점이 한 개일 때

- 내접할 때

두 반지름의 차가 두 좌표간의 차랑 같으면 내접한다.

(𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  =  ∣𝑟₂ - 𝑟₁∣

를 풀면 (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  =  (𝑟₂ - 𝑟₁)² 

 

 

- 외접할 때

두 좌표간의 거리가 반지름의 합과 같으면 외접이다.

(𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  =  𝑟₂ + 𝑟₁

를 풀면 (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  =  (𝑟₂ + 𝑟₁)² 

 

조건을 다 찾았다. 위 조건을 만족하지 않는다면 접점은 무조건 2개이다.

 

 

 

 

찾아본 바로는 double형으로 문제를 풀면 안된다.

double distance = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));

좌표 비교 시 == 연산자를 사용해야 하는데 double형은 근사치로 처리하기 때문에 조금의 오차가 생기는 경우 틀리게 된다.

 

 

 

[JAVA/백준] 1002번 문제 답

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		int T = in.nextInt();
 
		while (T-- > 0) {
 
			//조규현
			int x1 = in.nextInt();
			int y1 = in.nextInt();
			int r1 = in.nextInt();
 
			//백승환
			int x2 = in.nextInt();
			int y2 = in.nextInt();
			int r2 = in.nextInt();
			
			System.out.println(tangent_point(x1, y1, r1, x2, y2, r2));
		}
 
	}
 
	// 접점 개수 구하는 함수
	public static int tangent_point(int x1, int y1, int r1, int x2, int y2, int r2) {
    
    	// 중점간 거리 distance의 제곱 
		int distance_pow = (int)(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
 
 
		// case 1 : 중점이 같으면서 반지름도 같을 경우
		if(x1 == x2 && y1 == y2 && r1 == r2) {
			return -1;
		}
		
		// case 2-1 : 두 원의 반지름 합보다 중점간 거리가 더 길 때 
		else if(distance_pow > Math.pow(r1 + r2, 2)) {
			return 0;
		}
 
		// case 2-2 : 원 안에 원이 있으나 내접하지 않을 때 
		else if(distance_pow < Math.pow(r2 - r1, 2)) {
			return 0;
		}
		
		// case 3-1 : 내접할 때 
		else if(distance_pow == Math.pow(r2 - r1, 2)) {
			return 1;
		}
        
		
		// case 3-2 : 외접할 때 
		else if(distance_pow == Math.pow(r1 + r2, 2)) {
			return 1;
		}
		
		else {
			return 2;
		}
		
	}
 
}

가장 대중적인 Scanner를 이용하여 문제를 풀었다.

더 빠르게 동작하는 알고리즘은 아래 사이트에서 확인할 수 있다.

 

 

참고 사이트 https://st-lab.tistory.com/90