まず、点 \((s_x, s_y)\) と点 \((t_x, t_y)\) を半径 \(0\) の円と見なし、それぞれ円 \(0\) および円 \(N+1\) と見なすことにします。

頂点 \(0, 1, \dots, N+1\) からなる \(N+2\) 頂点のグラフを考えます。 頂点 \(i\) (\(0\le i\le N+1\)) は円 \(i\) に対応するとします。 円 \(i\) と円 \(j\) が交わるとき（判定は 公式解説 を参照）頂点 \(i\) と頂点 \(j\) の間に辺を張るとし、頂点 \(0\) と頂点 \(N+1\) の連結性判定をすればよいです。

連結性判定には union-find を使えばよいです。辺の本数が最大になるとき、\(\Theta(n^2)\) 回の操作を行うため、最悪計算量は \(\Theta(n^2)\) 時間です。

計算量に関して

頂点数が \(n\) の union-find に対して \(m\) 回操作を行うときの計算量は \(\Theta(n+m\cdot\alpha(m, n))\) 時間であり、\(m = \Theta(n^2)\) ならば \(\alpha(m, n) = \Theta(1)\) です。

他にも、\(m = \Omega(n\log(n))\) や \(m = \Omega(n\log^{\star}(n))\) のときも \(\alpha(m, n) = \Theta(1)\) になることが示せます。参考