Description:
XY平面上に点がN個散らばっている。(1<=N<=300)
半径1の円の中に点を最大何個収めることが出来るか?
各点のX,Y座標は0以上10以下で、どの2点も0.0001より近くなく、
どの2点間の距離も1.9999以上2.0001以下となる事は無く、
どこに円の中心を置こうとも、点と円の中心との距離が0.9999以上1.0001以下となる点の数は2つ以下である。
Answer:
円の中に点が複数有る時、その円から点を漏らさない様にずらして、円の中にある点を2つ円周上に持ってくる事が出来る。
よって、解が2以上なら、円周上に2つ点を乗っけた円を全部探してしまえば、どれかは解になる
計算量はO(n^3)。
PKUだと制限時間が厳しい為、C++でcomplexやvectorを使うとTLEを貰うので注意。
点が一つだけの時や、どの2点間の距離も2より大きい時に、うっかり答えを0とかにしてしまわないように注意。
Source: