matsueushi | AtCoder ABC 181 F

\(r\) を動かした時に、動かす円の中心が存在できない範囲を考えてみる。壁もしくは障害物から距離 \(r\) 未満の位置に円の中心を配置することができないことを考えると、動かせない範囲は下の青色で示した領域の内部になる。

fig0

fig1

上の壁と下の壁が図で示した青色の領域を通じて繋がっていなければ円が通過でき、繋がっていれば円が通過できない。繋がっているか繋がっていないかはUnionFindで判定できる。

\(y=100\) と釘 \((x_i, y_i)\) が繋がっている <=> \(y_i + 2 r > 100\)
\(y=-100\) と釘 \((x_i, y_i)\) が繋がっている <=> \(y_i - 2 r < 100\)
釘 \((x_i, y_i)\) と釘 \((x_j, y_j)\) が繋がっている <=> \((x_i-x_j)^2 + (y_i-y_j)^2 < (2r)^2\)

これで \(r\) が与えられたときの判定方法がわかったので、あとは \(r\) を二分探索する。