らての精進日記

修行をします

aoj1132:Circle and Points

解法

適当に円を置いてみると、いくつかの点が中に入る。1つ以下の点しか含まない円を配置する方法は考察するまでもないので、ここでは2つ以上の点が入ったと仮定する。

まず、円を適当に動かしてみる。(簡単のため、これによって新たに内包される点が増加することは考えない)
すると、いつか円周上に点が乗る。この状況で、その点を中心として円を回してみると、円周上に点が2つ乗る。

上記の操作によって、内包された点の数は、増えることはあっても減ることはない。
よって、円周上に点が2つ乗っているような円のみを見るだけでよい。

したがって、入力で与えられる点の中から任意の2点を選んで、その2点を通る円を求め、内包される点の数を数え上げてそれらの最大値をとればいい。
2つの点を通る円を求めるのはそんなに難しいことではない(幾何的なmathを少しやるだけ)。


コーナーケースとしては、2点間の距離が2より大きい場合は、その2点を通るような円は存在しないので、continueしなければならない。

また、答えが1になるようなケースでは、2点を通るような円がどこにも存在しないので、上記のアルゴリズムでは一度も探索が行われない。
最大値を格納する変数を0で初期化していると、答えが0になってしまうので、1で初期化しておくといい。

コード