最小包含円
最小包含円シリーズ！！！ 問題へのリンク 問題概要 二次元平面上に 個の点がある。これを 個の円ですべて覆うようにしたいです。 これを実現できるような 個の円の半径の最大値として考えられる最小値を求めよ。 制約 考えたこと まず要素技術として、 通り…
最小包含円と、マッチングの二部構成問題 問題へのリンク 問題概要 個の円 ( と番号付けされている) と、 個の多角形 ( と番号付けされている) とが与えられる。 各円は、中心の座標と半径 各多角形は、各頂点の座標 が与えられる。すべての多角形が、いずれ…
AtCoder
AtCoder600点
ABC-F
幾何
端点のみを考える
探索候補を絞る
全探索
三角形
三角形の五心
緩和しても良い
解を変形していく(最適性を失わずに)
三分探索
山登り法
凸関数
連続最適化
最小包含円
幾何だ！！！！！ そして、こういうので「ギリギリを考える」というのは典型な感じ。 なお、僕は最小包含円のことを知らず、アドホックに解いたけど、ライブラリ貼るだけだったらしい... (その方が計算量も少ない) 他にも、三分探索でも解ける！！！ 問題へ…
