Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12323 - Inspecting Radars (この記事を編集する[管理者用])

Source

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

問題概要

極座標系式でN個 (10^4以下) の点が与えられる.
各点のrは1以上R未満,θは0以上360未満の整数.Rは100以下.角度の単位は度.
E回 (100以下) だけ,平面をスキャンする.それぞれのスキャンに対して,その範囲に入っている点の数の最大値を求める問題.
各スキャンでは,整数HとAが与えられ (Hは1以上R以下,Aは0以上360未満),
好きな整数hとαを選び,
 h <= r < h+H,α <= θ <= α+A
の範囲の点をスキャンできる.
問題分の図も参照のこと.

解法

最初に下処理する.
各マスに対して,左上とそのマスを対角線とする長方形の点の数をDPで求めておく.
すると,包除原理である長方形内にある点の数をO(1)で数えれる.dp[a+1][b+1]-dp[c][b+1]-dp[a+1][d]+dp[c][d]みたいな感じで.
後は,各クエリに対して,場所を愚直に全探索する.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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