外側の円に内接し, 内側の円に外接する円を考える. この中心を \(P(x, y)\), 半径を \(r\) として, \(A(a, 0), B(b, 0)\) とすると,

\[AP+BP = (a+r) + (b-r) = a+b\]

となる. すなわち2点からの距離の和が一定なので \(P\) の軌跡は楕円になる.

楕円の方程式は

\[\frac{(x-(a+b)/2)^2}{c^2} + \frac{y^2}{d^2} = 1\]

となる.

この楕円の長径は \((a+b)/2\) なので \(c = (a+b)/2\) である.

また, 焦点は \(\pm (b-a)/2\) なので,

\[\frac{b-a}{2} = \sqrt{c^2-d^2}\]

となり,

\[\begin{align} d^2 &= \left(\frac{a+b}{2}\right)^2 - \left(\frac{b-a}{2}\right)^2 \\ &= ab \end{align}\]

となる. これにより, \(P\) の \(x\) が求まれば,

\[y^2 = d^2 \left(1 - \frac{(x-c)^2}{c^2} \right)\]

で \(y\) を求めることができる.

また, \(AP = a+r\) なので,

\[r = \sqrt{(x-a)^2 + y^2} - a\]

で \(r\) も求めることができる.

ここまでが長かったが, 本題に入る. 最小の円の半径をなるべく大きくするには, できるだけ上下均等に右から詰めていくのがいい. \(n\) が奇数ならば \((a+b,0)\) を中心とする円が最初にあって, 上下に \((n-1)/2\) 個詰めることになる. \(n\) が偶数ならば上下対称になるように詰めることになる.

右から \(i\) 番目の円の中心を \(P_i(x_i, y_i)\), 半径を \(r_i\) とすると, \(i+1\) 番目と \(i\) 番目の円は接するので,

\[\sqrt{(x_{i+1}-x_i)^2+(y_{i+1}-y_i)^2} = r_{i+1}+r_i\]

となるはずである. \(x_{i+1}\) が大きくなれば左辺は小さくなるが右辺は大きくなる. よって, この \(x_{i+1}\) は二分探索で求めることができる.