ABC259D - Circumferences

考え方

$N$個の円を$1,...,N$の頂点に対応させ，円周が交わるなら辺を張った無向グラフを考える．

こうすれば，$(s_{x}, s_{y})$に対応する頂点の集合から，$(t_{x}, t_{y})$に対応する頂点の集合へ到達できるかを判定する問題に帰着する．

「中心が$(x_{1}, y_{1})$で半径が$r_{1}$の円」と「中心が$(x_{2}, y_{2})$で半径が$r_{2}$の円」が交わる条件は，図を描くとわかるように

\begin{aligned}
| r_{1} - r_{2} |
\leq
\sqrt{(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}}
\leq
| r_{1} + r_{2} |
\end{aligned}

である．判定の際は2乗した条件

\begin{aligned}
(r_{1} - r_{2})^{2}
\leq
(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}
\leq
(r_{1} + r_{2})^{2}
\end{aligned}

で考えるとよい．

回答例

from collections import deque

N = int(input())
sx, sy , tx, ty = map(int, input().split())
XYR = [list(map(int, input().split())) for _ in range(N)]

G = [[] for _ in range(N)]
for i in range(N):
    xi, yi, ri = XYR[i]
    for j in range(i, N):
        xj, yj, rj = XYR[j]
        d2 = (xi - xj) ** 2 + (yi - yj) ** 2
        if (ri - rj) ** 2 <= d2 <= (ri + rj) ** 2:
            G[i].append(j)
            G[j].append(i)

start = set()
goal = set()
for i in range(N):
    x, y, r = XYR[i]
    if (x - sx) ** 2 + (y - sy) ** 2 == r ** 2:
        start.add(i)
    if (x - tx) ** 2 + (y - ty) ** 2 == r ** 2:
        goal.add(i)

q = deque(start)
seen = [False] * N
while q:
    cur = q.popleft()
    seen[cur] = True
    if cur in goal:
        exit(print('Yes'))
    for chi in G[cur]:
        if not seen[chi]:
            q.append(chi)

print('No')