2015年6月20日土曜日

AOJ 1164 : 締まっていこう

問題:

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 件のコメント:

コメントを投稿

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...