AtCoder Beginner Contest 151：F - Enclose All

問題
解法
解答

問題

https://atcoder.jp/contests/abc151/tasks/abc151_f

解法

求める半径を二分探索で求める．

半径を r に決めたとき，任意の 2 点を円の中心，半径を r とした円の交点は 2 つに定まる．そして，この 2 点それぞれを円の中心，半径を r とした円 2 つが N 個全ての点を内部または周上に含むかどうかを判定すればよい．このような円が 1 つでもあれば半径 r は十分な大きさだと分かる．1 つもなければ r よりも大きい半径を考える必要があると分かる．O(N^3 * log(ans))．