最小全域木を作る問題に帰着できる.

このとき, \(x\) 座標で昇順に並べたときに, \(x_i \leftrightarrow x_{i+1}\) の道しか考えなくてもいい. なぜなら, \(x_i \leftrightarrow x_{i+2}\) の道は \(x_i \leftrightarrow x_{i+1}\) の道と \(x_{i+1} \leftrightarrow x_{i+2}\) の道でカバーできるからである.

\(y\) 座標についても同様に考える.

最小全域木を作る方法で, 道をコストの昇順に並べ, Union-Find でコストの小さい順につないでいく.