2004/Contest/国内予選/Problem D

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)