[Baekjoon] # 1002: 터렛

터렛

문제

조규현과 백승환은 터렛에 근무하는 직원이다. 
하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 

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

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

예제

• 입력

  3
  0 0 13 40 0 37
  0 0 3 0 7 4
  1 1 1 1 1 5
  

• 출력

  2
  1
  0
  

  ---

Solution

def get_inputs():
    import sys

    input_data = sys.stdin.read()
    inputs = input_data.splitlines()

    item_count = int(inputs[0])

    string_to_int_arr = lambda x: list(map(int, x.split()))
    data = list(map(string_to_int_arr, inputs[1:]))

    return item_count, data


def solution(data):
    """
    이 함수는 좌표 6개의 리스트를 입력으로 받습니다:
    - (x1, y1, d1, x2, y2, d2)

    함수는 두 원의 관계를 나타내는 정수를 반환합니다:
    - -1: 두 원이 동일 (중심과 반지름이 동일함).
    - 0: 두 원이 서로 교차하지 않거나 떨어져 있음.
    - 1: 두 원이 외부 또는 내부에서 접함.
    - 2: 두 원이 두 점에서 교차함.
    """
    x1, y1, d1, x2, y2, d2 = data

    if x1 == x2 and y1 == y2:
        if d1 == d2:
            return -1
        else:
            return 0

    distance = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** (1 / 2)

    max_d = max(d1, d2, distance)

    remaining_sum = d1 + d2 + distance - max_d

    if remaining_sum > max_d:
        return 2
    elif remaining_sum < max_d:
        return 0
    else:
        return 1


def main():
    _, data = get_inputs()

    result = [solution(d) for d in data]

    print(*result, sep="\n", end="")


if __name__ == "__main__":
    main()

---

해결 방법

---

1. 서로 다른 세 점과 삼각형

• 내가 생각한 방법

가정

• 서로 다른 세 점은 3개의 서로 다른 거리를 형성한다.
• 이 세 거리 중 가장 긴 거리를 max_d라고 하자.
• max_d를 제외한 나머지 두 거리의 합을 remaining_distances라고 하자.

삼각형

1. remaining_sum > max_d : 세 점은 삼각형을 이룬다.
   • 이 경우, 있을 수 있는 좌표 수는 2
2. remaining_sum = max_d : 세 점은 직선을 이룬다.
   • 이 경우, 있을 수 있는 좌표 수는 1
3. remaining_sum < max_d : 세 점은 삼각형을 이루지 못 한다.
   • 이 경우, 있을 수 있는 좌표 수는 0

• 만약 주어진 두 점이 같을 경우
  • 주어진 거리도 같은 경우, 있을 수 있는 좌표 수는 -1(inf)
  • 주어진 거리가 다른 경우¹, 있을 수 있는 좌표 수는 -0

---

2. 원을 사용한 다른 방법

가정

• 주어진 거리를 d1, d2라고 하자
• 주어진 좌표 사이의 거리를 d라고 하자

원

한 점과 같은 거리를 가지는 점들의 집합

• 주어진 두 좌표와 거리는 2 개의 원을 이룬다.

1. d < d1 + d2인 경우, 두 원이 두 점에서 만난다.
   • 있을 수 있는 좌표 수는 2
2. d = d1 + d2인 경우, 두 원이 한 점에서 만난다.
   • 있을 수 있는 좌표 수는 1
3. d = d1 + d2인 경우, 두 원이 만나지 않는다.
   • 있을 수 있는 좌표 수는 0

• 만약, 두 원의 중심이 같을 경우,
  • d1 = d2인 경우, 두 원은 같다.
    • 있을 수 있는 좌표 수는 -1(inf)
  • 아니면, 두 원은 만나지 않는다.
    • 있을 수 있는 좌표 수는 0

두 방법은 수학적으로 같다

• 중심이 서로 다른 두 원은 만나서 삼각형을 이루거나 접하거나 만나지 않는다.

---

의사 코드

입력: data = [x1, y1, d1, x2, y2, d2]

만약 x1 == x2 그리고 y1 == y2:
    만약 d1 == d2:
        반환 -1  # 두 원이 동일 위치에 있고 반지름이 같음
    그렇지 않으면:
        반환 0   # 두 원이 동일 위치에 있지만 반지름이 다름

거리 계산:
distance = sqrt((x1 - x2)^2 + (y1 - y2)^2)

최대값 찾기:
max_d = max(d1, d2, distance)

나머지 합 계산:
remaining_sum = d1 + d2 + distance - max_d

결과 결정:
만약 remaining_sum > max_d:
    반환 2   # 두 원이 두 점에서 교차함
만약 remaining_sum < max_d:
    반환 0   # 두 원이 교차하지 않음
그렇지 않으면:
    반환 1   # 두 원이 한 점에서 접함

---

URL

• 터렛

1. 누가 계산 틀렸어…! ↩︎