9040: [yosupo] Geometry - Euclidean 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 $\sqrt{(x _ i - x _ j)^2 + (y _ i - y _ j)^2}$.
Calculate a minimum spanning tree of this graph.
For each $i$ , $j$, we add edge between them and whose weight is $\sqrt{(x _ i - x _ j)^2 + (y _ i - y _ j)^2}$.
Calculate a minimum spanning tree 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
$u _ 0$ $v _ 0$
$u _ 1$ $v _ 1$
:
$u _ {N - 2}$ $v _ {N - 2}$
Output all those $N-1$ pairs of $u _ i$ , $v _ i$ as the indices of the points that are the terminals of the edges in a minimum spanning tree.
If there are multiple solutions, print any of them.
$u _ 1$ $v _ 1$
:
$u _ {N - 2}$ $v _ {N - 2}$
Output all those $N-1$ pairs of $u _ i$ , $v _ i$ as the indices of the points that are the terminals of the edges in a minimum spanning tree.
If there are multiple solutions, print any of them.
Constraints
- $1 \leq N \leq 2\times 10^5$
- $|x _ i|, |y _ i| \leq 10,000$
- $|x _ i|, |y _ i| \leq 10,000$
Sample 1 Input
5
-1 -1
-6 4
-9 -7
2 5
-7 6
Sample 1 Output
0 1
0 2
0 3
1 4