Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12537 - Radiation (この記事を編集する[管理者用])

Source

An Asian Regional contest to be decided, ACM ICPC Hatyai Regional Contest 2012 Semilive (2012-11-18)
UVa 12537

問題概要

二次元平面上にN個 (200000以下) 家がある.座標が与えられる.
2つの原子力発電所A, Bが与えられる.座標が与えられる.
Q個 (20000以下) のクエリに答える問題.
各クエリでは,発電所Aに対する半径R1とBに対する半径R2が与えられる.
発電所Aからの距離がR1以下の家には防災グッズが与えられる.
発電所Bからの距離がR2以下の家には防災グッズが与えられる.
防災グッズが2個もらった家の人は,防災グッズがもらえなかった家の人に上げることができる.
防災グッズを所持できない家の数の最小値を求める問題.
各半径は13000以下の正整数,各座標は20000以下の非負整数.

解法

結局は,max(0, N-もらえる防災グッズの数)が答え.
各発電所からの距離で家をソートしておくと,各発電所からもらえる防災グッズの数は二分探索ですぐ求まる.
半径が整数で小さいので累積和みたいなのを求めておいても良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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