Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12435 - Consistent Verdicts (この記事を編集する[管理者用])

Source

World Finals Warmup I (2012-02-25)
UVa 12435

問題概要

2次元平面上の格子点にN人の人がいる.(Nは1000以下)
それぞれの人が順番に銃を鳴らす.
ある実数があって,距離R以下で鳴らされた銃の音は聞こえる.
自分の銃以外で,何個の銃が聞こえたかという配列のを考える.
その配列は何種類考えうるかを求める問題.

解法

最初0で,Rを増やしていくと徐々に増えていく.
基本的には,聞こえる聞こえないの閾値はC(N,2)ぐらいあるので,C(N,2)+1が答えになる.
が,2点間の距離が同じ組があればそのぶん縮退して答えが少なくなる.
2点間の距離を列挙して,異なるものが何個あるかを数える.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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