nanikaka https://blog.hatena.ne.jp/nanikaka/ nanikakaのAOJ航海日誌 https://nanikaka.hatenadiary.org/ AOJ Volume24 問題リンク Milky Way 解法 星を頂点、辺のコストを星間の最短移動距離としたグラフの最短経路を求めるのが方針です。 グラフの最短経路はワーシャルフロイドが短く書けるのでこれを使いました。 問題は星と星の間の距離をどう求めるかです。これは星を線分の集まりと考えて、線分同士の距離の中で最短のものを星間の最短距離と考えます。 星は見た目通り、5本の線分で構成されています。まずは、その線分の端点になっている5つの頂点の座標を求めます。 まず、星の中心を原点と考えます。ここで単位ベクトル(0, 1)をa度回転し、長さをR倍します。計算すると (x, y) = ( -sin(a*PI/180) *… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnanikaka.hatenadiary.org%2Fentry%2F20120619%2F1340046881" title="AOJ2402 Milky Way - nanikakaのAOJ航海日誌" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-06-19 04:14:41 rich https://nanikaka.hatenadiary.org/entry/20120619/1340046881 1.0 100%