[백준 알고리즘][자바] 1002번 : 터랫

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

1002번: 터렛

문제가 복잡해 보이지만 요약한다면 좌표평면 위에 두 점(조규현의 좌표, 백승환의 좌표)이 주어졌을 때,

각각 좌표에서 r1, r2만큼 떨어져 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성합니다.

단, 위치의 갯수가 무한대 일 경우에는 -1을 출력합니다. 

 

어떤 하나의 좌표에서 거리 r만큼 떨어져 있을 수 있는 점들의 집합은 바로 반지름이 r인 원입니다.

 

따라서 류재명이 있을 수 있는 좌표는 두 개의 원을 그렸을 때 생기는 점들의 개수입니다.

두 개의 원으로 만들 수 있는 점은 아래와 같습니다.

1. 두개의 원이 일치할 때(무한개)
2. 두개의 원이 서로의 바깥에 존재하면서 접점을 가지지 않을 때
3. 하나의 원이 다른 원안에 존재하면서 접점을 가지지 않을 때
4. 내접할 때
5. 외접할 때
6. 두개의 교점을 가질 때

이 문제의 정답 비율이 20%대인 이유는 이러한 다양한 경우의 수가 존재하여 많은 반례가 존재하기 때문입니다.

두 개의 원이 서로의 바깥에 존재하느냐 하나의 원이 다른 원안에 존재하느냐 이 두가지를 먼저 생각할 수 있었다면 쉽게 접근할 수 있는 문제입니다.(하지만 저는 어려웠습니다. 한번 실패한 후 차근차근 따져서 생각해내었습니다.)

 

두 점 사이의 거리

1. 두개의 원이 일치할 때 - x1 = x2, y1 = y2, r1 = r2

2. 두개의 원이 서로의 바깥에 존재하면서 접점을 가지지 않을 때 - xy_distance > r1 + r2

 

3. 하나의 원이 다른 원안에 존재하면서 접점을 가지지 않을 때 - xy_distance < r1 - r2

이 경우의 수가 잘 이해가 되지 않는다면 xy_distance를 점점 늘려갈 때 원의 위치를 상상하신다면 이해할 때 도움이 됩니다.

4. 내접할 때 - xy_distance = r1 - r2

3번의 경우의 수에서 xy_distance를 점점 늘려갈 때 같아지는 지점이 내접할 때입니다.

5. 외접할 때 - xy_distance = r1 + r2

6. 두 개의 교점을 가질 때 - 나머지

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			String[] str = br.readLine().split(" ");
			int x1 = Integer.parseInt(str[0]);
			int y1 = Integer.parseInt(str[1]);
			int r1 = Integer.parseInt(str[2]); // 반지름
			int x2 = Integer.parseInt(str[3]);
			int y2 = Integer.parseInt(str[4]);
			int r2 = Integer.parseInt(str[5]); // 반지름
			
			if(r1 < r2) {
				x1 = Integer.parseInt(str[3]);
				y1 = Integer.parseInt(str[4]);
				r1 = Integer.parseInt(str[5]);
				x2 = Integer.parseInt(str[0]);
				y2 = Integer.parseInt(str[1]);
				r2 = Integer.parseInt(str[2]);
			}
			
			double xy_distance = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)); // 좌표사이의 거리(원의 중심간의 거리)
			
			
			if(x1 == x2 && y1 == y2 && r1 == r2) { // 접점이 무한개 일 때
				bw.write("-1" + "\n");
			}
			else if(xy_distance > r1 + r2) { // 두개의 원이 밖에서 떨어져 있을 때
				bw.write("0" + "\n");
			}
			else if(xy_distance < r1 - r2) { // 한 원이 다른 원안에 있으면서 교점이 없을 때
				bw.write("0" + "\n");
			}
			else if(xy_distance == r1 - r2) { // 내접할 때
				bw.write("1" + "\n");
			}
			else if(xy_distance == r1 + r2) { // 외접할 때
				bw.write("1" + "\n");
			}
			else { // 그 밖에
				bw.write("2" + "\n");
			}
			
		}
		
		br.close();
		bw.flush();
		bw.close();
	}
}