Codeforces Round #514 (Div. 2) - D. Nature Reserve

問題リンク

解説

半径 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)でできました

提出コード

codeforces.com