1004_어린왕자

🍯 Comment

• 처음에는 하나의 원 정보를 입력받을 때마다, 출발/도착지점이 원 안에 있는지만 검사했음 원 안에 있다면, 해당 원을 지나야 한다고 생각함
  
• 하지만 틀렸습니다 보고 나서 다시 생각하면서 엣지 케이스를 넣어봤다 → 하나의 원안에 출/도착점모두 있는 경우가 있음!
  

⇒ 출/도착점이 하나의 원을 두고 안↔밖에 있어야, 하나의 진입/이탈이 성립된다

주석 메모

# 2초 / 128MB
# 23.05.20 
# 17:24 ~ 17: 57
# 행성간의 이동을 최대한 피해서 여행하기 -> 그래프, 정점간의 관계 예상

# 조건 1: 양쪽 점이, 주어진 원의 내부에 있는가 
    # 중점 cx, cy와 출/도착점 x,y의 거리랑 해당 원의 반지름이랑 비교
# 모든 원에 대해서, 출/도착점사이의 거리를 비교한다! 
    # 원 내부에 포함되어있으면 무조건 지ㅏㄴ야함

정답코드

import sys
input = sys.stdin.readline

from math import sqrt
T = int(input())

for t in range(T):
    # 출발점, 도착점
    x1, y1, x2, y2 = map(int, input().split())
    pos = []
    pos.append([x1,y1, True])
    pos.append([x2, y2, True])
    n = int(input())

    # 행성계의 중점 cx, cy, r
    ans_cnt = 0
    for i in range(n):
        cx, cy, r = map(int, input().split())

        # 출발,도착점에 대해 
        for k in range(2):
            dist = sqrt(pow((pos[k][0] - cx),2) + pow((pos[k][1] - cy),2))
 
            if dist < r:
                pos[k][2] = True
            else:
                pos[k][2] = False
        # 원을 기준으로 안/밖에 있으면
        if pos[0][2] != pos[1][2]:
            ans_cnt += 1
    print(ans_cnt)