[백준1002번/자바] 터렛

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

 

A(조규현), B(백승환), C(류재명)일 때,

A의 좌표 그리고 A와 C의 거리

B의 좌표 그리고 B와 C의 거리

가 주어진다.

 

이때 C의 좌표가 될 수 있는 가짓수를 구하면 된다.

 

굉장히 수학적인 느낌이라 알고리즘을 봤는데 수학, 기하학이 써있다.

수학 천재 친구에게 물었더니 '원' 키워드를 알려주었다. 

A-C의 거리, B-C의 거리를 원의 반지름으로 생각하고

A, B를 원으로 생각했을 때, C는 두 원의 접점이다.

그리고 접점의 개수는 0, 1, 2, 무한대 중에 하나이다.

 

r1 > r2라고 가정하겠다.

 

무한대

d == 0  &&  r1 == r2

 

만나지 않는 경우(0)

r1 + r2 < d  ||  d < r1 - r2

 

한 점에서 만나는 경우(1)

r1 + r2 == d  ||  r1 - r2 == d

 

두 점에서 만나는 경우(2)

r1 - r2 < d  &&  d < r1 + r2

 

---

코드로 작성해보자!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ1002 {
    public static void main(String[] args) throws IOException {
        // 1. 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        // 2. 계산
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < t; i++) {
            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());

            double d = getDistance(x1, y1, x2, y2);

            if(r1 >= r2) {
                result.append(findContact(result, r2, r1, d, r1 + r2) + "\n");
            } else {
                result.append(findContact(result, r1, r2, d, r1 + r2) + "\n");
            }
        }

        // 3. 출력
        System.out.println(result);
    }

    private static int findContact(StringBuilder result, int r1, int r2, double d, int i2) {
        if(d == 0 && r1 == r2) {
            return -1;
        } else if(d < r2 - r1 || i2 < d) {
            return 0;
        } else if(i2 == d || r2 - r1 == d) {
            return 1;
        } else {
            return 2;
        }
    }

    static double getDistance(int x1, int y1, int x2, int y2) {
        double d;
        int xd, yd;
        yd = (int) Math.pow((x1 - x2), 2);
        xd = (int) Math.pow((y1 - y2), 2);
        d = Math.sqrt(yd + xd);
        return d;
    }
}

 

 

 

내 코드가 시간이 많이 짧은 편(80ms)이라 다른 사람 코드를 확인해 봤다.

다른 사람들은 Math.abs 등 다양한 메서드를 사용해서 나보다 조금 더 시간이 걸린거 같다.

 

Math.abs는 절대값 구하는 메서드! 기억해두자!