Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

PKU 3747 - Scout YYF II (この記事を編集する[管理者用])

Source

POJ Monthly Contest - 2009.08.23
PKU 3747

問題概要

2次元平面上で,原点中心,半径Rの中が基地.
基地の中に自分と10個以下の爆弾がある.
爆発すると爆弾中心でとあるスピードで通れない場所が膨れる.
自分はそのスピードと同じ速度で走れる.
爆発に巻き込まれる前に基地の外に辿り着けるかどうかを判定する問題.

解法

2次元幾何(垂直二等分線 + 凸多角形のカット).
自分と爆弾の位置が一致したら不可能.
後は,2次元平面全体から初めて,各爆弾と自分との垂直に等分戦の自分側のみからなる領域を求めて(そこに全速力ダッシュしたら爆発に巻き込まれる前に辿り着ける場所の集合),それが基地の外と共通部分をもつかどうかを調べる.
カットした多角形の頂点のみを調べれば十分.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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