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

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

多角形

AOJ 3217 Cafe au lait (OUPC 2020 I)

数学っぽい問題好き!!! 問題へのリンク editorials 問題概要 個のカフェオレがある。 番目のカフェオレは、コーヒーが mg、ミルクが mg だけ入っている (ともに整数)。 これらを混ぜて作れるカフェオレのうち、コーヒー量 とミルク量が がともに正の整数…

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 つの凸…