けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

凸カット

AOJ 2385 Shelter (JAG 冬合宿 2010 day4-G) (700 点)

ボロノイ図の応用問題! 問題へのリンク editorials 問題概要 頂点数 の凸多角形があって、その内部に 個の点が与えられる。凸多角形の内部に一様ランダムに点を打つとき、以下の値の期待値を求めよ。 「その点 から 個の点までの距離の最小値」を二乗した値…

AOJ 2160 Voronoi Island (JAG 夏合宿 2009 day2-F) (450 点)

ボロノイ図 問題へのリンク editorials 問題概要 頂点の凸多角形と、その内部に 個の点が与えられる。それらの各 個の点に対して、以下の問に答えよ。 凸多角形のうち、その点に最も近い領域の面積を求めよ 制約 考えたこと まさにボロノイ図を求めよ、とい…

AOJ 3049 A Polygon And Circles (ACPC 2018 day2-K)

ボロノイ図!! 問題へのリンク editorial 問題概要 頂点の凸多角形と、 個の点が与えられる。以下の条件を満たす最小の正の実数 を求めよ。 個の点を中心とした半径 の円を考える 凸多角形の周および内部のどの点も、いずれかの円に包含される 制約 考えた…