[백준] 1002번 : 터렛 - Java

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

1002번: 터렛

---

---

알고리즘

조규현 A
백승환 B

A 터렛의 위치(𝑥₁, 𝑦₁)
B 터렛의 위치(𝑥₂, 𝑦₂)

마린(류재명) C
A와 B가 자신의 위치로부터의 거리 각각 계산

A부터 C까지의 거리 𝑟₁
B부터 C까지의 거리 𝑟₂

➡ 𝑥₁, 𝑦₁, 𝑟₁, 𝑥₂, 𝑦₂, 𝑟₂ 가 주어졌을 때 C가 있을 수 있는 위치의 수 찾기

각 터렛의 위치를 중심으로 C와의 거리를 반지름으로 하는 원 그리기
➡ 반지름이 𝑟₁ 인 A 와 반지름이 𝑟₂ 인 B 의 접점의 개수

---

두 원의 접점의 개수 구하는 경우의 수

1. 두 원의 중심이 같고 반지름도 같을 때(= 접점의 개수가 무한할 때)

• 𝑥₁ = 𝑥₂, 𝑦₁ = 𝑦₂, 𝑟₁ = 𝑟₂

---

2. 접점이 없을 때

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

• ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  > 𝑟₁ + 𝑟₂ ➡ (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  > (𝑟₁ + 𝑟₂)²

 

 

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

• 반지름이 같지 않으면서 반지름의 차가 두 원 간의 중점 거리보다 큰 경우
• ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  <  ∣𝑟₂ - 𝑟₁∣ ➡ (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  <  (𝑟₂ - 𝑟₁)²

---

3. 접점이 한 개 일때

3.1. 내접할 때

• 두 반지름의 차가 두 좌표 간의 차와 동일 시 내접함
• ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  =  ∣𝑟₂ - 𝑟₁∣ ➡ (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  =  (𝑟₂ - 𝑟₁)² 

 

3.2. 외접할 때

• 두 좌표간의 거리가 두 반지름의 합과 같으면 외접
• ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  =  𝑟₂ + 𝑟₁ ➡ (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  =  (𝑟₂ + 𝑟₁)² 

---

4. 위 조건들 불만족 시 : 접점 2개

---

좌표 간의 거리 구할 때 주의점

• ( (𝑥₂ -𝑥₁)² + (𝑦₂ - 𝑦₁)² )½ 값 구하기 위해 double 타입으로 변수 선언하고 하기와 같이 푸는 경우

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

 

• 좌표 비교 시 == 연산자 사용하는데, double (or float) 타입일 때 오차 발생할 수 있음
• 부동소수점 타입이 정확한 값이 아니라 근사치로 처리하기 때문

class Main {
    public static void main(String[] args) {
    
        double a = 0.1;
        double b = 0.2;
        double c = 0.3;
        
        if(a + b == c) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
        //false 나옴
    }
}

 

➡ 거리 구할 때 Math.sqrt()가 아닌, 제곱되어 있는 형태 = (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² 로 쓰기

---

풀이

1. Scanner

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) {
    
        int distance_pow = (int) (Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));	//중점 간 거리 distance의 제곱 
 
        //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;
        }
    }
}

 

2. BufferedReader + StringTokenizer

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
			
            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) {
    
        int distance_pow = (int) (Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));	//중점 간 거리 distance의 제곱 
 
        //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;
        }
    }
}

 

3. BufferedReader + StringTokenizer + StringBuilder

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
 
        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의 제곱 
 
        //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;
        }
    }
}

---

성능

1. BufferedReader + StringTokenizer + StringBuilder
2. BufferedReader + StringTokenizer
3. Scanner

 

---

출처 : https://st-lab.tistory.com/90#recentComments