BOJ 1002 - 터렛 | 안성진

문제

두 터렛의 위치 (x1, y1), (x2, y2)와 각 터렛에서 적까지의 거리 r1, r2가 주어질 때, 적이 있을 수 있는 위치의 수를 구하는 문제이다. 각 터렛에서 적까지의 거리 조건은 원을 정의하며, 두 원의 교점의 개수를 구하면 된다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스에는 x1, y1, r1, x2, y2, r2가 공백으로 구분되어 주어진다. (-10000 ≤ x1, y1, x2, y2 ≤ 10000, 1 ≤ r1, r2 ≤ 10000)

출력

각 테스트 케이스마다 교점의 수를 출력한다. 무한히 많으면 -1을 출력한다.

예제

입력:

3
0 0 13 40 0 37
0 0 3 0 7 4
1 1 1 1 1 1

출력:

2
2
-1

풀이

핵심 아이디어: 두 원의 위치 관계를 중심 간 거리 d와 두 반지름 r1, r2를 이용해 분류한다. 정수 연산에서 제곱 비교를 사용해 부동소수점 오차를 피한다.

단계별 풀이:

두 원이 동일: 중심이 같고 반지름도 같으면 교점이 무한 → -1
외부에서 분리: d² > (r1+r2)² → 교점 없음 → 0
내부에서 분리: d² < (r1-r2)² → 교점 없음 → 0
내접 (내부 접촉): d² == (r1-r2)² → 교점 1개
외접 (외부 접촉): d² == (r1+r2)² → 교점 1개
두 점에서 교차: 나머지 경우 → 교점 2개

제곱을 사용하는 이유: sqrt 계산 없이 정수로 비교하여 부동소수점 오차를 방지한다.

코드

package com.ssafy.an.day199;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Day177BOJ1002수학 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
 
		int T = Integer.parseInt(br.readLine());
 
		while (T-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int r1 = Integer.parseInt(st.nextToken());
 
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			int r2 = Integer.parseInt(st.nextToken());
 
			sb.append(tangent_point(x1, y1, r1, x2, y2, r2)).append('\n');
		}
		System.out.println(sb);
 
	}
 
	public static int tangent_point(int x1, int y1, int r1, int x2, int y2, int r2) {
 
		int distance_pow = (int) (Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2)); // 중점간 거리 distance의 제곱
		if (x1 == x2 && y1 == y2 && r1 == r2) {
			return -1;
		}
 
		else if (distance_pow > Math.pow(r1 + r2, 2)) {
			return 0;
		}
 
		else if (distance_pow < Math.pow(r2 - r1, 2)) {
			return 0;
		}
 
		else if (distance_pow == Math.pow(r2 - r1, 2)) {
			return 1;
		}
 
		else if (distance_pow == Math.pow(r1 + r2, 2)) {
			return 1;
		}
 
		else {
			return 2;
		}
 
	}
}

복잡도

시간: O(T) — T개의 테스트 케이스 각각 O(1) 처리
공간: O(1) — 상수 개의 변수만 사용

문제

BOJ 1002 - 터렛

입력