12/07/02 22:33:24.51
>170
・中心(0,0)、半径1の単位円として一般性を失わない
・1点を (-1, 0)と決め打ちしても一般性を失わない
この条件下で、最近傍の点との距離を dist とした場合に n 点詰め込む処理を用意して、
dist に対して二分探索を行った。
詰め込む処理はある点を追加した時に、
1) その点を中心とした半径 dist の円と単位円の交点
2) その点を中心とした半径 dist の円と、今まで追加してきた各点を中心とする半径 dist の各円との交点
を次の候補として探索した。
n = 20 辺りから急激に遅くなる。
似た問題で URLﾘﾝｸ(en.wikipedia.org) があってその結果と比べると大体合ってそうな感じ。
URLﾘﾝｸ(ideone.com)