Problems Submissions
Register Login 質問(Gitter) GitHub

Manhattan MST

AC一覧

問題文

2次元平面上に $N$ 個の点が与えられる。$i$ 個目の頂点の座標は $(x_i, y_i)$ である。

2点間の距離をマンハッタン距離、つまり $|x_i - x_j| + |y_i - y_j|$ で定義するときの、MSTを求めよ。

制約

入力

$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$

出力

$X$
$u_0$ $v_0$
$u_1$ $v_1$
:
$u_{N - 2}$ $v_{N - 2}$

ただし、$X$ は木の重みの総和。 解が複数存在する場合、どれを返しても構わない。

サンプル

# 1

6
3 8
4 9
2 1
10 5
4 9
2 0
21
4 1
5 2
1 0
0 2
1 3

Forum


Timelimit: 5 secs