21.08.05 기록

백준 알고리즘 1002 풀이

🎆나의 풀이(메모리 14.1MB, 시간 144ms로 통과)

-좌표를 그려보니 두 원의 교점 개수를 구하는 문제인 것 같았다.
-두 원의 중심거리와 각 원의 반지름 합/차 관계에 따라 교점 개수를 얻을 수 있다.

공식 (d = 두 원의 중심거리, r1/r2 = 각 원의 반지름)

• 두 점에서 만난다 > r1 - r2 < d < r1 + r2 (r1 > r2)
  
• 한 점에서 만난다 > r1 + r2 = d 또는 r1 - r2 = d (r1 > r2)
  
• 만나지 않는다 > r1 + r2 < d 또는 d < r1 - r2 (r1 > r2)
  
• d = √(x1-x2)² + (y1-y2)²

-위 공식을 적용하여 문제 풀이를 했다.

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

  public class B1002 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringBuilder sb = new StringBuilder();
          StringTokenizer st;

          int testCase = Integer.parseInt(br.readLine());
          int x1, y1, r1, x2, y2, r2, dd, sum, sub;
          for(int i = 0; i < testCase; i++) {
              st = new StringTokenizer(br.readLine(), " ");
              x1 = Integer.parseInt(st.nextToken());
              y1 = Integer.parseInt(st.nextToken());
              r1 = Integer.parseInt(st.nextToken());
              x2 = Integer.parseInt(st.nextToken());
              y2 = Integer.parseInt(st.nextToken());
              r2 = Integer.parseInt(st.nextToken());

              //두 원이 일치하여 좌표가 무한 개인 경우
              if(x1 == x2 && y1 == y2 && r1 == r2) {
                  sb.append(-1).append("\n");;
                  continue;
              }

              //정수형으로 풀기 위해 제곱근이 아닌 제곱값을 사용했다.
              dd = (((x1-x2)*(x1-x2)) + ((y1-y2)*(y1-y2))); //d²
              sum = ((r1 + r2) * (r1 + r2));  //sum²
              if(r1 >  r2) { sub = ((r1 - r2) * (r1 - r2)); } //sub²
              else { sub = ((r2 - r1) * (r2 - r1)); }

              if(dd > sub && dd < sum) { sb.append(2); }  //두 점에서 만나는 경우
              else if(dd == sub || dd == sum) { sb.append(1); } //한 점에서 만나는 경우
              else { sb.append(0); }  //만나지 않는 경우
              sb.append("\n");
          }
          System.out.println(sb);
      }
  }

🎆해설(메모리 14.3MB, 시간 144ms로 통과)

-각 경우의 수를 if-else if문으로 구현하고, Math.pow()를 적용하여 풀이했다.
-Math.pow(a, b) - a의 b제곱값을 리턴한다. (값은 모두 double형이다.)

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

  public class B1002 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringBuilder sb = new StringBuilder();
          StringTokenizer st;

          int testCase = Integer.parseInt(br.readLine());
          int x1, y1, r1, x2, y2, r2;
          while(testCase-- > 0) {
              st = new StringTokenizer(br.readLine(), " ");
              x1 = Integer.parseInt(st.nextToken());
              y1 = Integer.parseInt(st.nextToken());
              r1 = Integer.parseInt(st.nextToken());
              x2 = Integer.parseInt(st.nextToken());
              y2 = Integer.parseInt(st.nextToken());
              r2 = Integer.parseInt(st.nextToken());

              sb.append(getCount(x1, y1, r1, x2, y2, r2)).append("\n");
          }
          System.out.println(sb);
      }

      public static int getCount(int x1, int y1, int r1, int x2, int y2, int r2) {

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

          //case 1: 중점이 같으면서 반지름도 같은 경우 (무한)
          if(x1 == x2 && y1 == y2 && r1 == r2) { return -1; }

          //case 2-1: 두 원의 반지름 합보다 중점 간의 거리가 더 길 때 (만나지 않는 경우)
          else if (d > Math.pow(r1 + r2, 2)) { return 0; }

          //case 2-2: 원 안에 원이 있으나 내접하지 않을 때 (만나지 않는 경우)
          else if (d < Math.pow(r2 - r1, 2)) { return 0; }

          //case 3-1: 내접할 때(한 점에서 만나는 경우)
          else if (d == Math.pow(r2 - r1, 2)) { return 1; }

          //case 3-2: 외접할 때(한 점에서 만나는 경우)
          else if (d == Math.pow(r1 + r2, 2)) { return 1; }

          //case 4: 두 점에서 만나는 경우
          else { return 2; }
      }
  }