2012-08-22から1日間の記事一覧
問題リンク Chain-Confined Path 解法 ダイクストラで解きました。 頂点は両端の円の中心と、円の交点たちです。 面倒なのが、点Pと点Qの線分全体が円の内部にあるかという判定です。 図を見ると、円の内部を通るような線分は、2つの交点の間を通っています…
問題リンク Chain-Confined Path 解法 ダイクストラで解きました。 頂点は両端の円の中心と、円の交点たちです。 面倒なのが、点Pと点Qの線分全体が円の内部にあるかという判定です。 図を見ると、円の内部を通るような線分は、2つの交点の間を通っています…