터렛

1002번: 터렛 (acmicpc.net)

1002번: 터렛

두 원의 교점이 2개인 경우를 구하는 것만 따져보자. 삼각형 세 변의 길이를 알면 제 2 코사인 법칙으로 모서리의 코사인 값을 얻을 수 있다. 코사인 역함수로 라디안 값을 얻으면 이걸로 삼각함수를 실행해서 다른 변의 길이를 구하여 교점을 얻을 수 있다. 한편 두 원의 중심을 잇는 직선의 각도 탄젠트 역함수로 얻어낼 수 있다. 이를 기준으로 라디안 값을 더하거나 빼서 두 개의 각을 얻는다. 이것이 두 원의 교점이 된다.

import math

T = int(input())

for _ in range(T):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())

    # 터렛 간의 거리를 구한다
    d = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

    # 두 원의 위치와 반지름이 일치할 경우 해는 무한대
    if not d and r1 == r2:
        print(-1)
    # 두 원이 접할 경우 해는 한 개
    elif d == r1 + r2 or d == abs(r1 - r2):
        print(1)
    # 원이 접하지 않거나, 내부에 있으면 해는 없음
    elif d > r1 + r2 or d < abs(r1 - r2):
        print(0)
    # 터렛 간의 거리보다 반지름의 합이 크면 교점은 두개가 있다
    else:
        '''
        http://www.ezformula.net/esne/aboard/m_Fcontents_viewer.php?fcode=1112227
        세 변의 길이를 알고 있으므로 삼각형 제 2코사인 법칙을 사용하여 각 B를 구한다
              /\
          c  /  \  b
            /    \
          B -------
               a
        # b^2 == a^2 + c^2 - 2ac * cosB ... B각에 대한 제 2코사인 법칙
        # cosB = (a^2 - b^2 + c^2) / 2ac ... 여기에 역함수를 취하면 
        # B = arccos((a^2 - b^2 + c^2) / 2ac) ... B각을 얻는다
        '''
        cosB = (r1 ** 2 - r2 ** 2 + d ** 2) / (2 * d * r1)
        B = math.acos(cosB)
        # 직선이 얼마나 기울었는지 아크탄젠트 함수로 각을 얻는다

        if y2 == y1 or x2 == x1:
            A = 0
        else:
            A = math.atan((y2 - y1) / (x2 - x1))

        rad0 = A + B
        rad1 = A - B

        ix0 = x1 + r1 * math.cos(rad0)
        iy0 = y1 + r1 * math.sin(rad0)
        ix1 = x1 + r1 * math.cos(rad1)
        iy1 = y1 + r1 * math.sin(rad1)

        count = 0
        validate = lambda v : -10000 <= int(v) <= 10000

        for x, y in ((ix0, iy0), (ix1, iy1)):
            if all(validate(v) for v in (x, y)):
                count += 1

        print(count)