AOJ 2402 - 天の川

問題
提出コード

解法

任意の五芒星から別の五芒星に向かう際に通る最短距離さえ計算できれば、あとはベガからアルタイルに向けてダイクストラ法で最短経路を計算すればよいです。

五芒星は5本の線分でできています。ということで、2つの五芒星の最短距離を調べる際は、それぞれ5本の中から1本ずつ線分を取り出し、2本の線分同士の最短距離を計算して、25通りの取り出し方の中で最も小さいものを距離とすればよいです。
ということで、2本の線分同士の距離を求めることができればいいことになりました。
2本の線分同士の最短距離は、少なくともどちらか片方の線分については端点が選ばれます(片方の線分を点のあつまりとみなし、もう一方の線分との距離が最短になる点を探していくとどちらか一方は端点になります)。 ということで、4つの端点に対し、点と線分の距離を求めてあげれば、その中の最小値をとってあげることで、線分同士の最短距離を求めることができます。