\(r\) を固定して考えます。

平面上に \(2\) 点 \(A,B\) があるとします。 \(A,B\) 間の距離を \(\text{dist}(A,B)\) とすると、 \(2r≤\text{dist}(A,B)\) のとき \(AB\) 間を通ることができ、 \(2r>\text{dist}(A,B)\) のとき \(AB\) 間を通ることができません。
これは直線と点の場合でも同じで、直線 \(A\) と点 \(B\) の間の距離を \(\text{dist}(A,B)\) とすると、 \(2r≤\text{dist}(A,B)\) のとき \(AB\) 間を通ることができ、 \(2r>\text{dist}(A,B)\) のとき \(AB\) 間を通ることができません。

直線と釘を頂点とし、 \(2r>\text{dist}(x,y)\) となる頂点の間に辺を張った無向グラフを考えます。
\(2\) つの直線が同じ連結成分にある場合、明らかに円を \((-10^9,0)\) から \((10^9, 0)\) に移動させることはできません。
逆に、\(2\) つの直線が同じ連結成分にない場合、円を \((-10^9,0)\) から \((10^9, 0)\) に移動させることができます。 ( 右手法を使うと実際にルートを構成できることがわかります。 )

したがって、すべての頂点対について距離を求め、\(2\) つの直線が同じ連結成分になるまで距離の短い方から頂点対の間に辺を張っていくというアルゴリズムで \(O(N^2\log N)\) でこの問題を解くことができます。

回答例 (C++) : https://atcoder.jp/contests/abc181/submissions/17733698
回答例 (Python) : https://atcoder.jp/contests/abc181/submissions/17733487

BONUS : 実は \(O(N^2)\) で解くことができます。考えてみましょう。
追記 : 実は \(O(N \log N)\) で解くことができます。ヒント