蟻本にO(NlogN)になる理由などは述べられている。
実装だが、ここが本当にうまいと思った。
//a is sorted by x coordinate int m = n / 2; double x = a[m].fst; double d = min(closest_pair(a, m), closest_pair(a + m, n - m)); inplace_merge(a, a + m, a + n, compare_y);
xの昇順で真ん中のところに線を引きながら、yの座標でmerge sortを行っている。
これをすることで愚直にsortするとO(Nlog^2N)になるところを改善している。ほかの問題にも応用できそうだ。
あとinplace_mergeというのを使っているが、これがまさにmerge sortを行っている部分。
compare_yという関数を引数にしているが、これは単なるmergeでも指定できる。
mergeといえばデータ構造をマージする際の一般的なテクニックだが、使ったことがないので学習しておきたい。
