問題:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1164
簡単にいうと板に釘がいくつか打ち付けられていて、あとヒモが通っているのでヒモをピンッってした時のヒモの長さを答える問題。
解法:
引っかかっている釘、その直前に引っかかった釘、どれだけ巻き付いているか(角度)をスタックに入れる。角度は符号つき角度[-π, π]で考える。
ヒモABがACに連続的に移動する時を考える。
ABからACに移動する時に次に引っかかる釘をKとする。(もしそのような釘がなければK=Cとする)
この時, ∠BAKとスタックの先頭の角度を比較し
・それらが異符号ならばスタックの先頭は外れるので、
B ← pre(A)(Aの直前の釘)とAを結んだ直線と直線BCとの交点
A ← pre(A)
としてスタックをpopする。
・それらが同符号ならばスタックの先頭は外れないので、三角形ABC内の釘を凸法みたいな感じで選んでいき、スタックに入れていく。
解けた時は最高に「ハイッ」てやつだった。
https://gist.github.com/knewknowl/88bec89ce563a6755719
0 件のコメント:
コメントを投稿