Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4807 - Cocircular Points (この記事を編集する[管理者用])

Source

ACM/ICPC Latin America - South America - 2010/2011
UVa: ACM ICPC Latin America Regional Contest (2010-10-24) (blog)
LiveArchive 4807
SPOJ 7746 [MCOCIR] (2010-11-07 20:10追加)

問題概要

2次元平面上のN個 (100以下) の点が与えられるので,最も多くの点を通る円周を書いたとき,幾つの点の上を通るか求める問題.

解法

通る点を2つ固定して,その2つの点から,それぞれの点に向かって線を引き,角度を求める.
180度でなく,その角度が一致するものが,全部同一円周上に並べられる.
ただし,円に内接する四角形の対角の和は180度であることから,2点の線の逆側にあるものは180-x度にしてやる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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