競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ1132 Circle and Points

解法

ある点群を囲っている単位円について考えると,円から点がはみださないように円を動かしたとき,やがて円と2点がぶつかる.
このことから,いずれか2点がギリギリ円に含まれている全状態を考えれば漏れなく全探索を行うことができる.
2点の組み合わせはO(n^2)通りで,2点を通るような半径rの円は2通り存在するので,答えとなる可能性のある円の中心はO(n^2)通り.
あとは各円についていくつの点が含まれているかをO(n)で調べてやれば答えが出る.
注意点として,2点の距離が2以下でなければその2点を通るような円を構成することができない.