Problem#
給你一個陣列 points[i] = [x,y] 是在 2D 平面上的座標，令連接兩點的費用為兩點之間的曼哈頓距離(manhattan distance)
問你把圖聯通後且每個點到另一個點都只有存在一條簡單路徑，最小要花費多少？
測資限制#
- $1 \le n \le 1000$
- $-10^6 \le x_i, y_i \le 10^6$
- 點不會重複
想法#
題目要求最後兩點之間只會有一條簡單路徑，且整體權重最小 => 可以先把點連成網狀圖，在去找最小生成樹
- 時間複雜度: $\mathcal{O}(n^2\log{n^2})$
- sort: $O(n\log{n})$, 總共約有 $n^2$ 條邊
- 空間複雜度: $\mathcal{O}(n^2)$