[백준] 1002 - 터렛

문제

백준 1002번 터렛

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

 

 

문제 풀이

이 문제의 목적은 위치가 주어진 조규현과 백승환으로부터 류재명이 특정 거리만큼 떨어져 있을 때 류재명 위치 경우의 수를 구하는 것이다. 류재명이 있어야 하는 위치가 정수 좌표가 아니기 때문에, '중심'과 '거리'(반지름으로 해석할 수 있는)가 주어진 상황에서 '원'으로 접근할 수 있었다. 조규현과 백승환으로부터 특정 거리를 두고 위치할 수 있는 모든 류재명의 위치를 각각 원으로 두고, 원의 교점이 두 조건에 맞는 위치이다. 즉, 이 문제는 두 원의 교점을 찾는 문제이다. 

 

두 원의 위치 관계는 다음과 같은 경우로 나눌 수 있다.

 

처음 생각한 경우의 수는 다음과 같았다.

1. 두 원이 완전히 일치하는 경우 : 교점이 무한대이므로 -1
2. 중심은 같으나 반지름이 다른 경우 : 교점이 없으므로 0
3. 한 점에서 만나는 경우 : 1
4. 두 원이 거리를 두고 만나지 않는 경우  : 0
5. 그 외, 두 점에서 만나는 경우 : 2

그러나 두 원의 위치 관계에는 외접괴 내접이 있으므로, 빨간색으로 그린 것처럼, 

한 점에서 두 원이 만나는 경우에는 외접하는 경우와 내접하는 경우 두 가지가 있으며,

만나지 않는 경우에는 외부에서 두 원이 거리를 두고 만나지 않는 경우와 한 원이 다른 원의 내부에 있지만 교점이 없는 경우 두 가지를 추가적으로 고려해야 했다.

 

따라서 다음과 같은 모든 경우가 있다.

 

1. 두 원이 완전히 일치하는 경우 : 교점이 무한대이므로 -1
2. 중심은 같으나 반지름이 다른 경우 : 교점이 없으므로 0
3. 한 점에서 만나는 경우 
   3-1) 외접하는 경우 : 1
   3-2) 내접하는 경우 : 1
4. 두 원이 거리를 두고 만나지 않는 경우 
   4-1) 두 원의 거리가 0보다 큰 경우 : 0
   4-2) 한 원이 다른 원의 내부에 있으면서 교점이 없는 경우 : 0
5. 그 외, 두 점에서 만나는 경우 : 2

 

코드

모든 경우의 수를 반영한 코드는 다음과 같다.

import sys, math

input = sys.stdin.readline

t=int(input())
ans=[]

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

  r = math.sqrt((x1-x2)**2 + (y1-y2)**2)

  
  if (x1==x2) and (y1==y2):
    # 완전히 일치하는 경우
    if r1==r2:
      ans.append(-1)
    # 중심만 같고 반지름이 다른 경우
    else:
      ans.append(0)
  # 한 점에서 만나는 경우
  elif (r==r1+r2) or (r+min(r1,r2)==max(r1,r2)):
    ans.append(1)
  # 만나지 않는 경우
  elif (r>r1+r2) or (r+min(r1,r2)<max(r1,r2)):
    ans.append(0)
  # 두 점에서 만나는 경
  else:
    ans.append(2)

for a in ans:
  print(a)