Manhattan MST

AC一覧

Problem Statement
問題文

Given $N$ 2D-points. $i$-th is $(x_i, y_i)$.

For each $i, j$, we add edge between them and whose weight is $|x_i - x_j| + |y_i - y_j|$.

Calculate MST of this graph.

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

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

Constraints
制約

Input
入力

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

Output
出力

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

$X$ is the sum of weight of tree. If there are multiple solutions, print any of them.

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

Sample
サンプル

# 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

Before submitting, please confirm terms and conditions