1004번 문제풀이

백준 1004번 문제

배1004번 문제는 출발점에서 도착점까지 가는 길에서 행성에 진입/이탈하는 최소 횟수를 구하는 문제다.

문제 풀이과정은 다음과 같다.

문제풀이 과정

이 문제의 핵심은 거리는 최소가 아니라는 점에 있다. 

따라서 출발점과 도착점이 같은 원 안에 위치하는지가 중요하다. 

즉 둘 중 하나만 원 안에 있으면 +1 이되고, 그렇지 않은 경우는 모두 0이 된다.

이를 구현한 코드는 다음과 같다.

def check_InOrOut(point: tuple, planet:tuple):
  x, y = point
  a, b, r = planet
  d = ((x - a) ** 2 + (y - b)**2) ** 0.5
  if (d > r):
    return False
  else:
    return True


N = int(input())

for _ in range(N):
  x1, y1, x2, y2 = map(int, input().split())
  n = int(input())
  total_cnt = 0
  for _ in range(n):
    a1, a2, r1 = map(int, input().split())
    result1 = check_InOrOut((x1, y1), (a1, a2, r1)) # 출발점이 planet 안에 있는지
    result2 = check_InOrOut((x2, y2), (a1, a2, r1)) # 도착점이 planet 안에 있는지
    if (result1 != result2): total_cnt += 1 # 둘 중에 하나만 들어있으면 +1 해주기

  print(total_cnt)