解説

半径 $r$ に明らかに単調性があるので二分探索します。

以下、半径を $r$ とします。この時、円の方程式は中心を $(c, r)$ とすると、

$(x - c) ^ 2 + (y - r) ^ 2 = r ^2$

になります。

ある点 $(x _ {i}, y _ {i})$ が円の内部にある条件は、

$(x _ {i} - c) ^ 2 + (y _ {i} - r) ^ 2 \le r ^2$

$x _ {i} - \sqrt{r ^2 - ( y _ {i} - r) ^ 2 } \le c \le x _ {i} + \sqrt{r ^2 - (y _ {i} - r) ^ 2}$

となります。

よって、全ての $n$ の区間を含むような $c$ が存在するかを調べると二部探索ができるので、計算量は $O(n \log n)$ でできました

提出コード