Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11928 - The Busy Dog (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11928

問題概要

2次元平面上で,柱の座標と,移動経路が折れ線で与えられる.
移動経路の最初と最後は一致する.移動経路の折れ線の折れる部分の数は10000個以下.
柱の周りを正味何周回ったか(負もあり)を求める問題.
途中で柱に激突しているならそれを指摘する.

解法

柱と移動経路にそって三角形をつくって,柱の部分が作る角度を足していく.
すると,回った回数×2πぐらいになる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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