Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12320 - Flight Control (この記事を編集する[管理者用])

Source

XXV Colombian Programming Contest, The 2011 Colombia - XXV Maraton Nacional de Programacion ACIS / REDIS 2011 (2011-10-09)
UVa 12320

問題概要

3次元上の,2つの飛行機の移動経路とスピードが与えられる.
また,各飛行機のsecurity sphereの半径が与えられる.
security sphereとは,飛行機を中心として,与えられた半径の球で,それが接するか重なると危険とみなす.
危険になる回数を求める問題.
(危険状態から危険状態じゃなくなって,また危険状態になったら2回目をカウントする)
移動経路は100個以下の線分からなる折れ線.

解法

線分が切り替わる部分で分けて考える.その部分で,
1) 最初が危険,最後が危険 → ずっと危険なので増えない
2) 最初が危険,最後が危険でない → 危険から脱したので増えない
3) 最初が危険でない,最後が危険 → 危険になったので1回増える
4) 最初も最後も危険でない → 途中で危険になる可能性があるので,解析的or3分探索で最も近づく時刻を調べて,危険になってるかどうか調べる

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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