Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2069-051282ac
この記事にトラックバックする(FC2ブログユーザー)

UVa 12029 - Flying Spaceships (この記事を編集する[管理者用])

Source

Modified National Programming Contest of Bangladesh (2011-06-19)
UVa 12029

問題概要

3次元上の飛行機と,ある物体を考える.(両方共,無限に小さい点)
最初,飛行機の前向きはx軸に正の方向,飛行機の上向きはz軸に正の方向.
飛行機の3方向の回転と,前に進む,というコマンド列が与えられる.(1000コマンド以下)
その通りに移動したとき,飛行機と物体間の最小距離と,最大距離を求める問題.

解法

相対的に物体の方を回したり,移動させたりすると,各軸周りの回転のみ考えれば良い.
後は,各移動に対して,3分探索で最小距離を求めて,最大距離は端のどっちかになる.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2069-051282ac
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。