この問題は所謂「区間に辺を張るテク」を用いると、より直接的に解くことができます。

まずは頂点を \(x\) 座標でソートします。頂点 \(i\) からは \(x_i-K \le x_j \le x_i+K\) を満たす頂点 \(j\) 全てに対して辺が張られることになりますが、この時に \(j\) は一つの区間を成します。よって左右それぞれ二分探索を行って \(j\) が成す区間 \([l,r]\) を求め、頂点 \(i\) から区間 \([l,r]\) に向かって辺を張ることで目的を達成できます。 ここで問題文とは異なりますが、頂点 \(i\) から伸びる辺のコストを \(2c_i\) としてグラフを生成し、最終的にグラフ上で得られた最小コスト \(d\) に対して \(d-c_1+c_n\) を出力することにすると実装が簡潔です。\(\cdots \ \star\)

同時に \(y\) 座標に関しても同じことをする必要がありますが、これは以下のように実現できます。

• \(x\) 座標でソートしたときに \(i\) 番目となる頂点の \(y\) 座標は全体で \(p_i\) 番目に小さいとする。
• 頂点 \(i\) と頂点 \(N+p_i\) をコスト \(0\) の辺で双方向に結ぶ。
• 頂点を \(y\) 座標でソートして \(\star\) のように辺を張る。ただし、頂点 \(i\) から区間 \([l,r]\) に辺を張る代わりに頂点 \(N+i\) から区間 \([N+l,N+r]\) に辺を張る。

実装例

（コード内では 区間に辺を張るテクの実装例（Dijkstra法セット）と使用例 - Lorent’s diary で紹介されているクラスを使用させていただきました）