[Algorithm running]백준-터렛

* 문제

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.

조규현의 좌표 $(x_1, y_1)$ 와 백승환의 좌표 $(x_2, y_2)$가 주어지고, 조규현이 계산한 류재명과의 거리 $r_1$과 백승환이 계산한 류재명과의 거리 $r_2$가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

---

문제 해석

• 조규현을 기준으로 류재명이 있는 곳은 반지름 $r_1$의 원형 좌표이다.
  

그림의 주황선 어딘가에 류재명이 있다고 생각 할 수 있다.

• 백승환을 기준으로 류재명이 있는 곳은 반지름 $r_2$의 원형 좌표이다.
  

• 두 원형 좌표가 교차하는 지점의 수를 구하는 프로그램 작성.
  1점 교차 외접
  
  1점 교차 내접
  
  2점 교차
  
  무한한 접점
  
  접점 없음
  

접점의 개수 판별 방법
0. $d = \sqrt(x2-x1)^2 + (y2 - y1)^2$ => 두 중심점 사이의 거리

1. $d > r1 + r2$ => 0개(서로 떨어짐)
2. $d = r1 + r2$ => 1개(외접)
3. $|r1 - r2| < d < r1 + r2$ =>2개(내접, 외접)
4. $d = |r1 - r2|$ => 1개(내접)
5. $d < |r1 - r2|$ => 0개(원 안에 원)

---

거리 및 접점 계산 프로그래밍

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        double x1, x2, y1, y2, r1, r2, d;
    
        x1 =scanner.nextDouble();
        y1 =scanner.nextDouble();
        r1 =scanner.nextDouble();
        x2 =scanner.nextDouble();
        y2 =scanner.nextDouble();
        r2 =scanner.nextDouble();
        scanner.close();

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

        int a;
            if (d > r1 + r2) {
                a = 0; // 서로 떨어짐
            } else if (d == r1 + r2) {
                a = 1; // 외접
            } else if (d > Math.abs(r1 - r2) && d < r1 + r2) {
                a = 2; // 내접, 외접
            } else if (d == Math.abs(r1 - r2)) {
                a = 1; // 내접
            } else if (d < Math.abs(r1 - r2)) {
                a = 0; // 원 안에 원
            } else if (d == 0 && r1 == r2) {
                a = -1; // 동일한 위치 동일한 원
            } else{
                a = 0;
            }
        System.out.println(a);
    }
}

문제.1 동일한 위치 동일한 원의 조건일때 내접 조건으로 출력

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt(), i;

        for(i = 0; i < t; i++){
            double x1, x2, y1, y2, r1, r2, d;

            x1 =scanner.nextDouble();
            y1 =scanner.nextDouble();
            r1 =scanner.nextDouble();
            x2 =scanner.nextDouble();
            y2 =scanner.nextDouble();
            r2 =scanner.nextDouble();

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

            int a;
            if (d > r1 + r2) {
                a = 0; // 서로 떨어짐
            } else if (d == r1 + r2) {
                a = 1; // 외접
            } else if (d > Math.abs(r1 - r2) && d < r1 + r2) {
                a = 1; // 내접, 외접
            } else if (d == 0 && r1 == r2) {
                    a = -1; // 동일한 위치 동일한 원
            } else if (d == Math.abs(r1 - r2)) {
                a = 1; // 내접
            } else if (d < Math.abs(r1 - r2)) {
                a = 0; // 원 안에 원
            } else{
                a = 0;
            }

            System.out.println(a);
        }
        scanner.close();
    }
}

해결: 동일 위치 동일 원 조건을 내접 위로 이동

---

문제2. double 자료형 사용으로 부동소수점 오차 발생

if (d == r1 + r2) {  // 외접 조건

if (Math.abs(d - (r1 + r2)) < 1e-9) { 

해결: == 대신 Math.abs(a - b) <1e-9 사용

---

해답

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();
        for (int i = 0; i < t; i++) {
            int x1, y1, r1, x2, y2, r2;
            x1 = scanner.nextInt();
            y1 = scanner.nextInt();
            r1 = scanner.nextInt();
            x2 = scanner.nextInt();
            y2 = scanner.nextInt();
            r2 = scanner.nextInt();

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

            int a;
            if (d > r1 + r2) {
                a = 0; // 서로 떨어짐
            } else if (Math.abs(d - (r1 + r2)) < 1e-9) {
                a = 1; // 외접
            } else if (d > Math.abs(r1 - r2) && d < r1 + r2) {
                a = 2; // 두 점에서 만남
            } else if (Math.abs(d) < 1e-9 && r1 == r2) {
                a = -1; // 동일한 원 (무한대 접점)
            } else if (Math.abs(d - Math.abs(r1 - r2)) < 1e-9) {
                a = 1; // 내접
            } else if (d < Math.abs(r1 - r2)) {
                a = 0; // 원 안에 원
            } else {
                a = 0;
            }

            System.out.println(a);
        }
        scanner.close();
    }
}

---

TMI: 문제를 처음 봤을때 이게 무슨 소리인가... 하였다.
불필요한 글을 간추리고 나서야 해당 문제를 이해 할 수 있었다...