AOJ 1132 Circle and Points


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

AOJ1132 Circle and Points

解説

解法1

任意の二点を選んでその点を通る円を作る。円は2個ある。

そのような全ての円それぞれが包含できる点の数を数えて最大値を求める。N<=300なので間に合う。

円の中心点の求め方

選んだ2点a, bの作る直線Aの生む垂直二等分線と、2点のうち一方の点と中心を結ぶ長さ1の線分から、三平方の定理でAと中心の距離を求める。

後は、線分abの中点からaまたはbに向かうベクトルを90度回転してやれば、その位置が円の中心となる。

点を包含できるかの判定方法は、ベクトルを用いて円の中心を始点と考えた時の点までの長さと半径の比較で判定できる。