Tag: geometry

def distance(x1, y1, x2, y2, r_squared):
    dist_sq = (x2 - x1) ** 2 + (y2 - y1) ** 2
    return dist_sq <= r_squared

def solve():

    N, R, D, X, Y = map(int, input().split())

    graph = [[0, 0]]
    for _ in range(N):
        graph.append(list(map(float, input().split())))

    v = [False] * (N + 1)
    
    q = deque([(X, Y, 0)])
    
    result = 0.0
    
    r_sq = R * R

    while q:
        cur_x, cur_y, count = q.popleft()

        for i in range(1, N + 1):
            target_x, target_y = graph[i]

            if not v[i] and distance(cur_x, cur_y, target_x, target_y, r_sq):
                v[i] = True

                result += (D / (2 ** count))
                
                q.append((target_x, target_y, count + 1))

    print(result)
solve()

• $1000 ≤ x_1, y_1, x_2, y_2, c_y, c_x ≤ 1000$
• $1 ≤ r ≤ 1000$
• $1 ≤ n ≤ 50$
• 좌표와 반지름은 모두 정수

행성계를 꼭 통과해야 하는 조건을 먼저 찾는. 출발점이나 도착점이 행성계 안에 있을 경우 무조건 그 항성계를 통과해야 한다. 출발점이나 도착점을 포함하지 않고 있는 행성계는 어떻게든 피해갈 수 있기 때문이다.

한 점이 원 안에 포함되어있는지 확인하려면, 원의 반지름과 원의 중심과 그 점 사이의 거리를 비교하면 된다. 원의 반지름이 더 크다면 그 점은 무조건 원 안에 위치하게 되고, 원의 중심과 그 점 사이의 거리를 비교하면 그 점은 원 밖에 위치하게 된다.

t = int(input())
for _ in range(t):
    cnt = 0
    x1, y1, x2, y2 = map(int, input().split())
    n = int(input())
    for _ in range(n):
        c_x, c_y, r = map(int, input().split())
        r = r ** 2
        dis1 = (c_x - x1) ** 2 + (c_y - y1) ** 2
        dis2 = (c_x - x2) ** 2 + (c_y - y2) ** 2
        if (dis1 < r and dis2 < r) or (dis1 > r and dis2 > r):
            continue
        else:
            cnt += 1
    print(cnt)