次の問題を考えます。

• \(N\) 個の点があり、 \(i\) 番目の点は座標 \((i, P_i)\) である。この時、各点についてその点にマンハッタン距離が最も小さい点を求めよ。

この問題は元の問題と同値です。

さて、マンハッタン距離をコストとする最小全域木を考えてみましょう。

この時、各点について自身の周囲の辺のうち少なくとも一つはマンハッタン距離が最も小さいので、それを答えとすればよいです。

Manhattan MSTは \(O(N \log N)\) などで解くことができるので、この問題を解くことができました。