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

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

多角形

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 問題概要 頂点の凸多角形と、 個の点が与えられる。以下の条件を満たす最小の正の実数 を求めよ。 個の点を中心とした半径 の円を考える 凸多角形の周および内部のどの点も、いずれかの円に包含される 制約 考えた…

AOJ 3176 Plane Graph (HUPC 2020 day3-E)

原案でした!僕は比較的アドホック寄りの問題を作る傾向があったかもだけど、これは典型な感じ。 問題へのリンク 問題概要 頂点数 、辺数 の連結な平面グラフが与えられます。ここで、各頂点の座標 も入力として与えられます。 どの 3 点も一直線上にはあり…

円と多角形の共通部分の面積 (AOJ Course CGL_7_H)

円と多角形の共通部分の面積を求めるライブラリ、一念発起して整備した!!! サブルーチンとして「円と "線分" の交点を求める」というライブラリが必要となる。 問題へのリンク 問題概要 原点を中心とした半径 の円と、 頂点の多角形が与えられる。これら…

AOJ 2423 コードアートオンライン / Code Art Online

最小包含円と、マッチングの二部構成問題 問題へのリンク 問題概要 個の円 ( と番号付けされている) と、 個の多角形 ( と番号付けされている) とが与えられる。 各円は、中心の座標と半径 各多角形は、各頂点の座標 が与えられる。すべての多角形が、いずれ…

AtCoder AGC 021 B - Holes (黄色, 600 点)

駅メモ!駅メモ!駅メモ!!!!! 問題へのリンク 問題概要 座標平面上に 個の頂点がある。各頂点の座標は で与えられる。 原点を中心とする半径 の円内の点をランダムに選び、与えられた 個の点の中から最も近い距離にある点へと移動する。 各点について、…

AOJ 3056 Equilateral Triangle (RUPC 2019 day2-F)

計算量的な詰めが甘かった。二分探索要らなかった。 問題へのリンク 問題概要 凸な 角形が与えられる。この 角形を完全に含むような正三角形の一辺の長さの最小値を求めよ。 制約 考えたこと 座標系として くらいの大きさまであるので、EPS は くらいがいい…

AOJ 1089 Strawberry Cake

面積二等分系の第二弾 問題へのリンク 問題概要 頂点の凸多角形が与えられる。原点を通る直線であって、この凸多角形を面積が等分になるように切断するものを求めよ。複数ある場合はどれか 1 つ求めればよい。 制約 原点は凸多角形に内包される 考えたこと …

AOJ 2442 Convex Cut (JAG 夏合宿 2012 day3b-C) (400 点)

面積二等分系問題、こないだ ICPC アジア 2019 にも出ていた。そっちは超むずいけど、こっちは簡単。 問題へのリンク 問題概要 頂点の凸多角形が与えられる。以下の条件を満たす点 P を求めよ: P を通る任意の直線によって、凸多角形は面積の等しい 2 つの凸…