[백준 - S3] 1002. 터렛

문제

이 문제는 두 원의 위치 관계에 따라 교점의 개수를 판별하는 문제이다.
핵심은 두 원의 중심 간 거리와 반지름의 합 / 차를 비교하는 것이다.

 

먼저 두 원의 중심 사이 거리를 직접 구하지 않고 거리의 제곱값을 사용해 비교한다. 이는 sqrt 연산을 피함으로써 연산 비용을 줄이고 부동소수점 오차를 방지할 수 있다.

• d : 두 원 중심 사이 거리의 제곱
• sum : 두 반지름의 합의 제곱 → 외접 판단 기준
• diff : 두 반지름의 차의 제곱 → 내접 판단 기준

 

• 두 원의 중심이 같고 반지름도 같은 경우
  두 원이 완전히 일치하므로 교점의 개수는 무한대이다.
  → -1 출력
• 두 원이 서로 만나지 않는 경우
  • 중심 거리(d)가 반지름 합보다 큰 경우 → 서로 너무 멀리 떨어짐
  • 중심 거리(d)가 반지름 차보다 작은 경우 → 한 원이 다른 원 안에 있지만 접하지 않음
    → 교점 0개
• 두 원이 한 점에서 만나는 경우
  • 외접: 중심 거리 = 반지름 합
  • 내접: 중심 거리 = 반지름 차
    → 교점 1개
• 두 원이 두 점에서 교차하는 경우
  위의 모든 조건에 해당하지 않는 경우로 두 원이 서로 두 개의 교점을 가진다.
  → 교점 2개

 

제출 코드

public class Main {

    static int T, M;
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            String[] split = br.readLine().split(" ");
            int x1 = Integer.parseInt(split[0]);
            int y1 = Integer.parseInt(split[1]);
            int r1 = Integer.parseInt(split[2]);
            int x2 = Integer.parseInt(split[3]);
            int y2 = Integer.parseInt(split[4]);
            int r2 = Integer.parseInt(split[5]);

            dir(x1, y1, r1, x2, y2, r2);
        }

    }

    static void dir(int x1, int y1, int r1, int x2, int y2, int r2) {

        long dx = x1 - x2;
        long dy = y1 - y2;
        long d = dx * dx + dy * dy; // 거리의 제곱

        long sum = (long) (r1 + r2) * (r1 + r2);
        long diff = (long) (r1 - r2) * (r1 - r2);

        if (d == 0 && r1 == r2) {
            System.out.println(-1);
        } else if (d > sum || d < diff) {
            System.out.println(0);
        } else if (d == sum || d == diff) {
            System.out.println(1);
        } else {
            System.out.println(2);
        }
    }

}

 

문제 링크

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