nanikaka https://blog.hatena.ne.jp/nanikaka/ nanikakaのAOJ航海日誌 https://nanikaka.hatenadiary.org/ AOJ Volume11 問題リンク Chain-Confined Path 解法 ダイクストラで解きました。 頂点は両端の円の中心と、円の交点たちです。 面倒なのが、点Pと点Qの線分全体が円の内部にあるかという判定です。 図を見ると、円の内部を通るような線分は、2つの交点の間を通っています。よって、2点P、Qの線分が円の内部を通っているかは、PとQの間にある全ての交点対(円iと円i+1の2つの交点)の間を通っているかを調べればOKです。これは外積を用いることで簡単に判定できます。 全頂点間に対して辺を張れば後は単なるダイクストラです。 ソース 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnanikaka.hatenadiary.org%2Fentry%2F20120822%2F1345647152" title="AOJ1183 Chain-Confined Path - 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-08-22 23:52:32 rich https://nanikaka.hatenadiary.org/entry/20120822/1345647152 1.0 100%