AOJ 1132 - Circle and Points - ツバサの備忘録

解法

1個のみ円の中に入るパターンは明らかなのでここでは2個以上のパターンのみ考えます。
円の中に入る点の個数が最大の円の配置方法があるとき、その個数を減らさないまま、ある2点を同時に円周上に乗せることができます。
ということで、これ以降は2点が円周上にあるパターンの円の配置方法について、点の個数が最大となるパターンを探せばよいです。
f:id:emtubasa:20190811170916p:plain
ある距離が1以下の2点が存在するとき、上の図のような2つの円のパターンが存在します。それぞれについて、入る点の個数を求めれば良いです。
円の中心座標が求まれば、全部の点について、中心からの距離が1以下であるかどうかを調べ、1以下であるものをカウントすれば円の中に入る点の個数がわかります。
ということで、あとは円の中心座標がわかればよいです。
f:id:emtubasa:20190811172202p:plain
今、図の線分 $AB$ が2点を結ぶ直線だとします。この際の、中心座標を求めます。
$\angle ABC = 90^{\circ}$ です。
また、線分 $AC$ の長さは2で、 $AB$ も、2点の座標がわかっているので求めることができます。ということで、三平方の定理から、 $BC$ の長さも求めることができます。これにより、 $\overrightarrow{BA}, \overrightarrow{BC}$ を求めることができ、円の中心は $A$ と $C$ の中点なので、上手く計算することができます。
あとは、全部の円について中心を求め、その中に入る点の個数の最大値を計算すれば答えとなります。