読者です 読者をやめる 読者になる 読者になる

AOJ 1132 Circle and Points

任意の二点を選んでその点を通る円を作る。円は2個ある。
そのような全ての円それぞれが包含できる点の数を数えて最大値を求める。N<=300なので間に合う。
円の中心点の求め方
選んだ2点a, bの作る直線Aの生む垂直二等分線と、2点のうち一方の点と中心を結ぶ長さ1の線分から、三平方の定理でAと中心の距離を求める。
後は、線分abの中点からaまたはbに向かうベクトルを90度回転してやれば、その位置が円の中心となる。