Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 3270 - Simplified GSM Network (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3270

問題概要

2次元平面上に,携帯の電波塔が50個以下,町が50個以下,それぞれ座標が与えられる.
いくつかの街の間には直線の道路で結ばれている.
携帯電話は一番近い電波塔につながるとして,ある町からある町に移動するとき,電波塔の変更回数の最小値を求める問題.
電波塔の有効範囲の境界上に町があるとか,変なコーナーケースはないことが保証されている.

解法

強実装問題.
電波塔の有効範囲をボロノイ図を書いて調べる.
後は,それぞれの道路が,境界を何回跨ぐかを調べて,それを距離としてワーシャルフロイドか何かする.
サイズは小さいので全て非効率的な方法でも良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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