문제 링크

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

문제 해설

이 문제는 결국 두 원의 교점 개수를 구하는 문제이다.

문제에서는 조규현과 백승환의 좌표 (x₁, y₁)와 (x₂, y₂), 그리고 각각 적(류재명)까지의 거리 r₁과 r₂가 주어진다.
이를 수식으로 나타내면 다음과 같다.

류재명의 좌표를 (x, y)라고 하면, 류재명은 조규현을 중심으로 한 반지름 r₁의 원 위에 있어야 하며 동시에 류재명은 백승환을 중심으로 한 반지름 r₂의 원 위에도 있어야 한다.

즉, 두 개의 원의 교점 개수를 구하는 문제가 된다.

두 원의 교점 개수를 구하기 위해서는 두 원의 중심점 사이의 거리를 유클리드 거리 공식을 이용하여 두 점 사이의 거리를 구하고 이 거리를 이용하여 두 원의 위치 관계를 조건에 따라 분류해야 한다.

※ 유클리드 거리 공식: 두 점 사이의 거리를 구하는 공식

• ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½ < ∣𝑟₂ - 𝑟₁∣

1. 두 원의 접점의 개수가 무한대일 때

두 원의 접점의 개수가 무한대라는 것은 두 원이 완전히 정확하게 겹친 상태라는 뜻이다. 두 원이 완전하게 겹치기 위해서는 당연히 중심점의 좌표가 서로 같고 반지름의 길이도 서로 같아야 한다.

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

2. 두 원에 접점이 존재하지 않을 때(접점 개수가 0)

두 원의 접점이 존재하지 않다는 것은 두 원이 서로 만나지 않는다는, 서로 겹치지 않는다는 것이다. 여기에는 두 가지 경우가 존재한다.

2 - 1. 두 원이 서로 외부에 있는 경우

두 원의 중점 사이의 거리가 두 원의 반지름을 합친 것보다 더 크다.

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

2 - 1. 한 원이 다른 원에 겹치지 않게 있는 경우

이 경우 접점을 갖지 않으려면 반지름이 같지 않으면서 반지름의 차가 두 원간의 중점 거리보다 크면 된다.

( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½ < ∣𝑟₂ - 𝑟₁∣

3. 접점이 한 개일 때

3 - 1. 내접하는 경우

이 경우는 중심점 사이의 거리가 반지름의 차와 같으면 된다.

( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½ = ∣𝑟₂ - 𝑟₁∣

3 - 1. 외접하는 경우

이 경우는 중심점 사이의 거리가 반지름의 합과 같으면 된다.

( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½ = ∣𝑟₂ + 𝑟₁∣

접점이 두 개인 경우

접점이 두 개인 경우는 다음과 같이 오직 1가지이다.

( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½ < ∣𝑟₂ + 𝑟₁∣ and ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½ > ∣𝑟₂ - 𝑟₁∣

두 원의 중점 사이의 거리 구하기

두 원의 중점인 (x1, y1)와 (x2, y2) 사이의 거리는 ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½이다.
이는 코드로 다음과 같이 나타낼 수 있다.

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

하지만 double, float형은 부소수점 타입이어서 근사치로 나오기 때문에 오차 때문에 == 비교 힘들다.
따라서 Math.sprt()로 루트 형태로 쓰지 말고 제곱되어 있는 형태인 (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²을 사용하고 동시에 비교 대상인 반지름 r에 제곱한 값인 r²과 비교하자. 이를 코드로 나타내면 다음과 같이 나타낼 수 있다.

int dis = (int) (Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));

정답 코드(Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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(tangentPoint(x1, y1, r1, x2, y2, r2)).append("\n");
        }
        System.out.println(sb);


    }

    private static int tangentPoint(int x1, int y1, int r1, int x2, int y2, int r2) {
        
        // 조규현과 백승환의 사이의 거리(두 점 사이의 거리)
        int dis = (int) (Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));

        /* 1. 두 원의 접점의 개수가 무한대일 때 => 두 원이 완전히 겹침*/
        if (x1 == x2 && y2 == y1 && r1 == r2) return -1;


        /* 2. 두 원의 접점의 개수가 0일 때 => 두 원이 만나지 X */

        // 2 - 1. 두 원이 서로 완전히 떨어져 있다 -> 두 점 사이의 거리가 각 원의 반지름의 합보다 클 때 => ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  > 𝑟₁ + 𝑟₂ => (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  > (𝑟₁ + 𝑟₂)²
        else if (dis > Math.pow(r1 + r2, 2)) return 0;

        // 2- 2. 한 원 안에 겹치지 않는 다른 원이 있다  -> 반지름의 차가 두 원간의 중점 거리보다 크다 => ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  <  ∣𝑟₂ - 𝑟₁∣ => (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  <  (𝑟₂ - 𝑟₁)²
        else if (dis < Math.pow(r1 - r2, 2)) return 0;


        /* 3. 두 원의 접점의 개수가 1일 때 => 두 원이 한 점에서 만난다*/

        // 3 - 1. 두 원이 외접한다 -> 반지름의 합이 두 원간의 중점 거리와 같다 => ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  =  𝑟₂ + 𝑟₁ =>  (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  =  (𝑟₂ + 𝑟₁)²
        else if (dis == Math.pow(r2 + r1, 2)) return 1;

        // 3- - 2. 두 원이 내접한다 -> 두 반지름의 차가 두 좌표간의 차랑 같 => ( (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)² )½  =  ∣𝑟₂ - 𝑟₁∣ => (𝑥₂ - 𝑥₁)² + (𝑦₂ - 𝑦₁)²  =  (𝑟₂ - 𝑟₁)²
        else if (dis == Math.pow(r2 - r1, 2)) return 1;

        /* 4. 두 원의 접점의 개수가 2일 때 => 두 원이 두 점에서 만난다.*/
        else return 2;
    }


}