[Kotlin, S3] 백준 1002번 터렛

출처: unsplash.com

 

터렛(1002번)

Silver 3

#수학 #기하학 #많은 조건 분기

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

 

문제 내용

 

 

문제 접근

입력 형식을 보면 터렛의 좌표와 마린과의 거리가 나온다. 이를 이용해 원을 이용하는 문제임을 유추할 수 있다.

입력 예제 1의 첫 번째 case를 확인해 보자.

0 0 13 40 0 37

첫 번째 터렛의 좌표가 0, 0이고 마린과의 거리가 13이므로 반지름이 13인 원이라고 생각하면 된다.

사진 1-1

 

첫 번째 터렛을 기준으로 다음과 같이 원을 구성하면 원의 둘레에 해당하는 부분들이 모두 마린이 있을 수 있는 경우의 수인 것이다.

두 번째 터렛도 구성해 보자. 두 번째 터렛은 좌표가 40, 0이고 마린과의 거리는 37이다.

사진 1-2

 

두 번째 원은 다음과 같이 구성된다. 그럼 첫 번째 원을 원래 위치인 0, 0에 놓게 되면 다음과 같은 구조를 가지게 된다.

 

사진 1-3

 

두 원 간의 교점이 총 2개가 생겼다. 위 그림처럼 각 원의 둘레가 마린이 있을 수 있는 경우일 때 두 원의 교점이 몇 개인지 알 수 있으면 정답을 구할 수 있다. 입력 예제 1의 첫 번째 테스트 케이스의 정답은 2이다.

 

이를 통해 두 원의 관계를 이용해 교점의 개수를 구하면 되는 문제라는 것을 알았다.

두 원의 교점의 경우의 수는 총 4가지가 있다.

교점이 2개인 경우, 교점이 1개인 경우, 교점이 없는 경우, 교점이 무한개인 경우이다.

 

각 교점을 구할 수 있는 경우를 4개의 상황으로 나눠서 설명하겠다.

 

 

<상황 1>

먼저 교점이 무한개인 경우는 조금만 생각해 보면 각 터렛에서 마린이 있는 경우의 수인 원의 둘레가 정확히 일치하는 경우에만 무한대가 되는 경우가 된다.

두 원이 정확히 겹쳐지는 경우가 마린이 있을 수 있는 경우의 수가 무한개가 되는 것이다.

원 D안에 원 C 있음, 사진 2-1

이 경우를 체크하기 위해서는 두 터렛의 좌표가 같아야 하고 측정한 마린과의 거리도 일치해야 한다.

if (turret1X == turret2X && turret1Y == turret2Y && radius1 == radius2)

터렛의 좌표, 마린과의 거리가 모두 일치하는 경우에만 마린이 있을 수 있는 경우의 수가 무한개가 된다.

 

 

<상황 2>

두 번째 상황은 두 원의 교점의 개수가 1개인 경우이다.

이 경우는 2가지 경우를 생각해야 한다. 원이 내접하는 경우와 외접하는 경우이다.

첫 번째로 외접하는 경우부터 확인해 보자.

사진 2-2

위와 같은 경우에는 교점이 1개만 존재한다.

두 원이 외접하는 경우는 어떻게 코드로 작성해야 할까?

바로 두 원의 반지름의 길이의 합과 각 원의 중심의 좌표 간의 거리가 일치하게 되면 교점이 1개만 있는 경우가 된다.

else if (distanceTurret == radiusPlus)

두 터렛 좌표 간의 거리를 distanceTurret이라고 하고 두 원의 반지름의 합을 radiusPlus라고 할 때 두 값이 일치해야 한다.

 

두 번째 경우에는 원이 내접하는 경우이다. 원이 내접하는 경우는 다음과 같다.

사진 2-3

이 경우에는 어떻게 코드로 나타내야 할까?

이 경우에는 외접과 반대로 생각하면 된다. 원의 중심들 간의 거리와 두 원의 반지름의 차가 같으면 내접하는 경우가 성립된다.

else if (radiusMinus == distanceTurret)

두 반지름의 차를 radiusMinus라고 정의하고 distanceTurret과 비교한다.

 

 

<상황 3>

3번째 상황은 두 원의 교점이 0개인 경우이다. 이 때는 두 원이 서로 만나지 못하는 모든 경우가 있다.

두 원이 만나지 못하는 경우는 총 2가지로 나뉜다.

그중 한 가지 예를 보여 주자면 아래와 같다.

사진 2-4

위 사진의 경우에는 두 원은 서로 밖에 있으면서 만나지 못하고 있다.

이 상황은 외접하는 경우를 구했을 때와 동일한 공식을 쓰는데, 조건 1개만 바꿔준다.

두 중심 좌표 사이의 거리가 각 원의 반지름의 합보다 큰 경우에만 위와 같은 상황이 된다.

else if (distanceTurret > radiusPlus)

 

두 원이 서로의 바깥에 있으면서 만나지 못하는 경우를 구했으니, 이제 하나의 원이 다른 큰 원 안에 들어가 있지만 교점이 없는 경우도 확인해 봐야 한다.

사진 2-5

이 경우에는 외접 공식을 동일하게 이용하되, 조건을 바꿔야 한다.

두 점 사이의 거리가 두 원의 반지름의 차보다 작은 경우이다.

else if (radiusMinus > distanceTurret)

 

 

<상황 4>

이제 교점이 2개인 경우의 수만 남았다. 사실 교점이 2개인 경우의 수를 구하는 방법은

지금까지 있었던 모든 상황의 경우의 수를 만족하지 않으면 교점이 2개인 경우가 된다.

그림 2-6

교점이 2개인 경우는 너무 경우의 수가 많아서 위 상황들을 전부 만족하지 않았을 때가 교점이 2개인 경우이기 때문에 이를 처리해 주면 된다.

 

자세한 정보는 두 원의 위치 관계를 검색해서 공부해 보거나 아래의 블로그를 이용해서 공부해 보자.

https://houseofj.tistory.com/167

두 원의 중심거리에 따른 두 원의 위치 관계

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.abs
import kotlin.math.pow
import kotlin.math.sqrt

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()

    for (i in 0 until case) {
        val turret = readLine().split(" ").map { it.toDouble() }
        val (turret1X, turret1Y, radius1) = turret.subList(0, 3)
        val (turret2X, turret2Y, radius2) = turret.subList(3, 6)

        // 터렛의 좌포가 같고 반지름의 길이도 같으면 마린이 있는 경우는 무한대가 됨.
        if (turret1X == turret2X && turret1Y == turret2Y && radius1 == radius2) println(-1)
        else {
            // 두 점 사이의 거리 구하기.
            val distanceX = turret1X - turret2X
            val distanceY = turret1Y - turret2Y
            val distanceTurret = sqrt(distanceX.pow(2) + distanceY.pow(2))

            val radiusPlus = radius1 + radius2
            val radiusMinus = abs(radius1 - radius2)
            // 접점이 0개인 경우: 두 점 사이의 거리가 두 원의 반지름의 길이의 합보다 클 때, 또는 두 반지름의 차가 두 점 사이의 거리보다 클 때
            if (distanceTurret > radiusPlus || radiusMinus > distanceTurret) println(0)
            // 접점이 1개인 경우: 두 점 사이의 거리가 두 원의 반지름의 합과 같을 떄, 또는 두 반지름의 차가 두 점 사이의 거리와 같을 때
            else if (distanceTurret == radiusPlus || radiusMinus == distanceTurret) println(1)
            // 접점이 2개인 경우: 두 점 사이의 거리가 두 원의 반지름의 합보다 작을 때
            else println(2)
        }
    }
}

 

문제 풀이

터렛 2개의 좌표와 각 터렛이 측정한 마린과의 거리를 입력받는다.

터렛의 좌표와 마린과의 거리를 이용해 원을 구성하고 두 좌표 간의 거리와 두 터렛이 측정한 마린과의 거리의 합과 차를 각각 저장한다.

 

그리고 각 상황에 맞도록 조건을 작성해서 교점의 개수를 출력해 주면 된다.

 

 

문제 해결 과정

두 원의 위치 관계를 이용해야 하는 문제이다.

수학을 공부하고 있는 학생들에게는 실버 이하의 문제가 되겠지만, 나 같은(?) 사람들은 문제 이해부터 힘겨워할 것이다.

두 원의 위치 관계를 파악하지 못하면 절대 해결할 수 없는 문제이다.

 

두 원의 교점이 몇 개인지의 조건을 정확하게 명시해야 한다.

교점이 없는 경우와 1개인 경우는 성립되는 조건이 2가지씩 있다는 것을 명심하자.

또한 정수로 입력을 받지만 제곱근과 제곱을 사용하기 때문에 소수점 차이로 오답이 나기 쉽다. 내 경우에는 25%에서 틀리더라.

sqrt()를 사용하는데 틀렸다고 뜨면 sqrt를 지우고 pow를 이용해서 문제를 해결하자.