Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 259 D問題 Circumferences

AtCoder ABC ABC259 D問題 400 pts

問題

提出解答

問題の概要

$N$ 個の円 $C_1, \dots, C_N$ がある. $C_i$ の中心は $c_i=(x_i, y_i)$ , 半径は $r_i$ である.

2点 $s=(s_x, s_y), t=(t_x, t_y)$ が与えられる. 次のことは可能か?

$s$ から少なくとも1つの円の円周上である点を通って, $t$ に到達可能.

ただし, $s,t$ は共にある円周上の点である.

制約

$1 \leq N \leq 3000$
$-10^9 \leq x_i, y_i \leq 10^9$
$1 \leq r_i \leq 10^9$
$s,t$ はある円周上の点

解法

以下のことが成り立つ.

2つの円 $C,D$ に対して, $C$ 上の任意の点 $a$ と $D$ 上の任意の点 $b$ において $a$ から $b$ へ $C,D$ の円周上を辿って到達可能であることの必要十分条件は $C,D$ が共有点を持つことである.

また, $C,D$ が共通部分を持たない場合は, $C$ 上の任意の点 $a$ と $D$ 上の任意の点 $b$ において $a$ から $b$ へ $C,D$ の円周上を辿って到達不可能である

2つの円 $C,D$ において, 2つの円の中心の距離を $d$ , 2つの円の半径をそれぞれ $r,s$ とするとき, 以下が成り立つ.

$C,D$ のうち, 一方が他方に含まれる $\iff d \lt \left|r-s \right|$
$C,D$ は内接する $\iff d=\left|r-s \right|$
$C,D$ は交わる $\iff \left|r-s \right| \lt d \lt r+s$
$C,D$ は外接する $\iff d=r+s$
$C,D$ のうち, 一方の外部に他方が含まれる $\iff d \lt r+s$

このことから, $C,D$ が共有点を持つことの必要十分条件は $\left|r-s \right| \leq d \leq r+s$ である.

これらの事実から, 次のような無向グラフ $G=(V,E)$ を作成すればよい. ただし, 2点 $p,q$ の距離を $\operatorname{dist}(p,q)$ と書くことにする.

$V:=\{1,2, \dots, N\}$
$E:=\{ij ; \left|r_i-r_j \right| \leq \operatorname{dist}(c_i, c_j) \leq r_i+r_j \}$

このとき, 点 $s$ が円 $c_k$ の円周上の点, 点 $t$ が円 $c_l$ の円周上の点であったとしたとき, $k,l$ が $G$ において同じ連結成分上の点かどうかをみればよく. 同じ連結成分上の点ならば可能, そうで無いならば不可能である *1.

時間計算量については各 $i,j$ に対して, $ij \in E$ かどうかを調べる必要があるため, $O(N^2)$ である.

*1: $k,l$ の候補はそれぞれ複数ある場合があるが, このような場合でも $G$ の定義から結果は取り方に依らないことがわかる.