AOJ1132 : Circle and Points

最適解が2点以上含む場合は、そのうちの2点を通る円でその最適解を必ず構成できる。

最適解を構成する頂点の集合をSとする。(|S|>=2)。Sの外側の点だけを拾って凸包を構成する。ただし、Sの点が一直線上に並ぶ場合は線分を構成する。これをTとおく。Sの点をすべて含むような円で、円周上には点が2個未満であるものを考えてみる。このとき、Tの隣接する2点以上に接してかつ、T上の点がすべて円の外側に出ないように円を動かすことができるはず。よって、この場合も最適解は|S|である。

そこで、与えられた頂点のうち2個を総当たりで選んで固定し、それらを通る円の中心を求め、そこからの距離が1以下の頂点を数えればいい。全体で計算量はθ(N³)となる。

2点A, Bを通る円の中心の求め方は以下の通り。A, Bの中点をMとする。また円の中心をCする。点Cから点Aへの距離は半径の1。線分AMの長さは、線分ABの長さの半分。よって、三角形AMCに三平方の定理を使ってCMの長さが求まる。ABの法線で長さが1であるものをとおく。すると中心Cの座標は より求まる。