ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

幾何

AOJ 2402 - 天の川

問題 提出コード 解法 任意の五芒星から別の五芒星に向かう際に通る最短距離さえ計算できれば、あとはベガからアルタイルに向けてダイクストラ法で最短経路を計算すればよいです。 五芒星は5本の線分でできています。ということで、2つの五芒星の最短距離を…

AOJ 2003 - Railroad Conflict

問題 提出コード 解法 経路は線分で、入力が与えられた時点で全て決まっているため、選ぶことができるのはどの箇所を地上に、どの箇所を地下にするか、です。 新しくつくる路線が既存の路線と交差する地点もはじめから決まっているので、それらはあらかじめ…

ARC064 E - Cosmic Rays

問題 提出コード 解法 あるバリア内は好きな座標に移動できます。 ので、あるバリアから、別のバリアへと移動することを考えます。 そのとき、2つのバリアについて重複する箇所が存在すれば、そのバリア同士は自由に行き来することができます。そうでないと…

AOJ 1132 - Circle and Points

問題 提出コード 解法 1個のみ円の中に入るパターンは明らかなのでここでは2個以上のパターンのみ考えます。 円の中に入る点の個数が最大の円の配置方法があるとき、その個数を減らさないまま、ある2点を同時に円周上に乗せることができます。 ということで…

ABC130 C - Rectangle Cutting

問題 提出コード 解法 2つに分かれる長方形の面積の差を縮めることを考えると、長方形の面積をちょうど半分に分けるような直線を引くのが最適になります。 与えられている点と、長方形の中心(対角線の交点)を通るような直線を引くと、面積を半分に分けること…

ABC016 D - 一刀両断

問題 提出コード 解法 分割される部分が1つ増えるには、線分ABと交差する多角形の辺が2本増える必要があります。 交差する多角形の辺が奇数になることは必ず存在しないので、多角形の辺と交差する辺の本数を2で割り、最後に1追加したものが答えとなります。 …

AOJ 2233 - Carrot Tour

問題 提出コード 解法 これ自力で解ききれなかったの悔しいですね… dp[i][j][k] = k回目の移動でiからjに移動するときの、それまでの移動距離の合計の最小値 とします。こうすることで、持っているにんじんの個数は自動的にkになります。 そして、 dis[i][j]…

AOJ 2600 - Koto Distance

問題 提出コード 解法 サンプルの図がわかりやすいのですが、ある座標(x,y)から距離w以内に効果がある場合、 (x-w,p)~(x+w,p)および(p,y-w)~(p,y+w)の範囲に効果があることになります。ここで、pは任意の数字になります。これは、横についてx-w~x+wの範囲を…

AOJ 1175 - そして,いくつになった?

問題 提出コード 個人的にICPCの中でも結構好きな部類の問題です。 解法 今回もc言語です。 メモ化再帰をしていきます。 円盤の枚数はたかだか24で、状態としては”残っている”か、”取り去られている”の2通りです。なので、全体で種類の状態が存在しますが、…

AOJ 1190 - つながれた風船

問題 提出コード 二度とやりたくないです。。。 今回は諸事情でC言語となっています。 自分は高校数学がとてもできないので、今回もさまざまなサイトにお世話になりました。 四面体の体積を求める2つの公式with行列式 | 高校数学の美しい物語 ヘロンの公式…

AOJ 1194 - バンパイア

バンパイア 提出コード 初めての幾何問題です。 まずはのときの、x座標がの部分の太陽の高さを求めます。 ビルの左右の端が小数になることはないので、は整数の座標の部分のみ求めます。太陽の高さはの右側が単調減少、左側は単調増加となっているからです。…