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 の円」を求めるのにはいくつも方法はあると思うけれど、その一例。 上図で、太線部が直角三角形であることと二点間の距離、長さ 1 の辺から、角度 α が α = arccos(d) で求まる。 また、上図の角度 θ も容易に求まるので、目的とする円の中心座標 (x, y) は (x, y) = ( x1 + cos(θ+α), y1 + sin(θ+α) ) として求められる。 もう片側の円の中心に対しても同様。 (三廻部; Jun 6, 2004) 議論・その他 †
ファイルを添付する †mikurube_D2.mdrw 1623件 [詳細] mikurube_D2.png 1663件 [詳細] mikurube_D1.mdrw 1252件 [詳細] mikurube_D1.png 1314件 [詳細] mikurube_D.c 1731件 [詳細] |