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