[백준 1002번] 터렛, 두 원의 교점의 개수

문제 링크: 1002번 터렛

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

 

반지름이 r1, r2인 두 원은 다음과 같은 위치 관계를 가질 수 있다.

 

1. 서로 다른 두 점에서 만난다.

|r2-r1| < d < r2+r1

 

2. 한 점에서 접한다.

2-1. 외접

r1+r2 = d

 

2-2. 내접

|r2-r1| = d

 

3. 만나지 않는다.

3-1. 한 원이 다른 원의 외부에 있을 경우

d > r1+r2

 

3-2. 한 원이 다른 원의 내부에 있을 경우(반지름이 다른 동심원 포함)

d < |r2-r1|

 

4. 무수히 많은 점에서 만난다(반지름이 같은 동심원).

두 원의 중심이 같고, r1 = r2

 

그런데 이 문제를 풀 때, d를 구할 때에는 점과 점 사이의 거리 공식을 이용해야 하고, 이는 기본적으로 피타고라스 정리를 이용한 것이다. 곧, d를 구하기 위해서는 제곱근을 이용할 수밖에 없다.

이는 실수 자료형을 이용하게 하고, 곧 코드는 오차로 인한 오답의 위험성을 내포하게 된다. 이를 방지하고자 d와 r1+r2, r1-r2를 비교하는 것이 아니라 d^2과 (r1+r2)^2, (r1-r2)^2을 비교하여 정수형으로만 문제를 풀 수 있다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int test = Integer.parseInt(br.readLine());
        while (test-- > 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());

            int sqd = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);

            int rs = (r1 + r2) * (r1 + r2);
            int rd = (r1 - r2) * (r1 - r2);

            if (x1 == x2 && y1 == y2 && r1 == r2) {
                sb.append(-1);
            } else if (sqd > rs) {
                sb.append(0);
            } else if (sqd == rs) {
                sb.append(1);
            } else if (rd < sqd) {
                sb.append(2);
            } else if (sqd == rd) {
                sb.append(1);
            } else {
                sb.append(0);
            }

            sb.append('\n');
        }

        System.out.print(sb);
    }
}

 

참고로, 아래 코드는 내가 PS를 처음 시작했을 때 짠 코드로서 오차를 고려하지 않았다. 통과는 하지만, 좋은 코드라고 할 수는 없다.

 

#include <iostream>
#include <cmath>
using namespace std;

int main(void) {
    int x1, y1, r1, x2, y2, r2;
    double d;
    int cases; cin >> cases;
    
    for (int i = 0; i < cases; i++) {
        cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
        d = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
        int rdiff = r1 - r2 > 0 ? (r1-r2) : (-1) * (r1-r2);

        if (d == 0 && r1 == r2) {
            cout << -1;
        } else if (d > r1 + r2) || d < rdiff) {
            cout << 0;
        } else if (d == r1 + r2) || d == rdiff) {
            cout << 1;
        } else if (d < r1 + r2) {
            cout << 2;
        }
        cout << '\n';
    }
    
    return 0;
}