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

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

凸包

AtCoder ABC 356 G - Freestyle (5D, 赤色, 575 点)

この見た目で「幾何」になるの、面白い! 問題へのリンク 問題概要 高橋君は 種類の泳ぎ方ができる。 種類目の泳ぎ方では、1 秒間に体力を だけ消費して、 メートル進むことができる。このとき、次の 回のクエリに答えよ。 【クエリ】 正の実数 が与えられる…

AOJ 2373 HullMarathon (JAG 冬合宿 2010 day3-E) (700 点)

面白い最適化問題! 問題へのリンク 問題概要 二次元平面上で、原点からの距離が であるような 点の凸包の面積として考えられる最大値を求めよ。 制約 考えたこと 凸包というところが面倒だが、要は 本のうちの何本かを選んで それを適切な順序に並び替えた…

AtCoder ABC 207 D - Congruence Points (黄色, 400 点)

すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…

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

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

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

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

TopCoder SRM 401 DIV1 Hard - NCool (本番 5 人)

最近、ABC 201〜300 の D 問題埋めを推奨している身としては、僕も同様のトレーニングとして SRM 401〜650 辺りの DIV1 Hard 埋めを始めてみようと思い立った。 問題へのリンク editorial へのリンク 問題概要 二次元平面上において、以下の条件を満たす線分…