- 470 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 01:27:09 ]
- >>468
動的ボロノイ図を使えば，一反復が O(n + k log n) でできる．
ただし k は引き離す必要のあるペアの数．
ただ，これは実装が結構しんどいので，現実的には
x 座標でソートしたリストを盛っておいて，x 座標の近い順に見て
枝刈りするのが有力だと思う
（x 座標が一定距離を超えたら，距離が一定距離以下にはならない等）
計算量は最悪 O(n^2) だから変わってないけれど，現実的には改善されるはず．
なお，ソートは最初の一回だけ行えば，あとは引き離したところだけ更新すると
多少の効率化ができる．
