8217: [yosupo] Geometry - Manhattan MST
[Creator : ]
Description
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.
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.
Input
$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$
$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.
$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.
Constraints
$1 \leq N \leq 200,000$
$0 \leq x_i, y_i \leq 10^9$
$0 \leq x_i, y_i \leq 10^9$
Sample 1 Input
6
3 8
4 9
2 1
10 5
4 9
2 0
Sample 1 Output
21
4 1
5 2
1 0
0 2
1 3