人権なし

競プロで解いた問題や開発の進捗などの記録です

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)).

解答

https://atcoder.jp/contests/abc151/submissions/9471462

f:id:babcs2035:20200112223421p:plain