2004/Contest/国内予選

Problem D : Circle and Points

問題概要

実数平面上に散りばめられた点の集合を半径 1 の円でできるだけ多く囲みたい。最も多く囲める点の数を出力せよ。

解法

基本的には、円周上に二点を乗せる半径 1 の全ての円を探索すればいいかな、と。計算量は、円の列挙に O(点の数^2) で、その円に対する点の探索に O(点の数) が必要。 (三廻部; Jun 3, 2004)


2003 World Finals, Problem E: Covering Whole Holes と気分的には似たような感じで。 (三廻部; Jun 6, 2004)


「円周上に二点を載せる半径 1 の円」を求めるのにはいくつも方法はあると思うけれど、その一例。

mikurube_D1.png

上図で、太線部が直角三角形であることと二点間の距離、長さ 1 の辺から、角度 α が

α = arccos(d)

で求まる。

mikurube_D2.png

また、上図の角度 θ も容易に求まるので、目的とする円の中心座標 (x, y) は

(x, y) = ( x1 + cos(θ+α), y1 + sin(θ+α) )

として求められる。

もう片側の円の中心に対しても同様。 (三廻部; Jun 6, 2004)

議論・その他

  • 下のプログラムはろくに誤差を考えていないバージョンだから微妙な予感。誰か検証して〜。 (三廻部; Jun 3, 2004)
  • 正解データと比較させてもらいました。大丈夫っぽい。 (三廻部; Jun 6, 2004)

ファイルを添付する

filemikurube_D2.mdrw 551件 [詳細] filemikurube_D2.png 616件 [詳細] filemikurube_D1.mdrw 568件 [詳細] filemikurube_D1.png 644件 [詳細] filemikurube_D.c 683件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filemikurube_D2.mdrw 551件 [詳細] filemikurube_D2.png 616件 [詳細] filemikurube_D1.mdrw 568件 [詳細] filemikurube_D1.png 644件 [詳細] filemikurube_D.c 683件 [詳細]

Last-modified: 2009-11-06 (金) 13:25:51 (3243d)