分数: 500 点
问题陈述
有 N 飞机上的城镇。的 i第-个城镇位于坐标处 (x_i,y_i)。同一坐标处可能有多个城镇。
您可以在坐标处的两个城镇之间修建一条道路 (a,b) 和 (c,d) 费用为 min(|a-c|,|b-d|) 日元(日本的货币)。不可能修建其他类型的道路。
你的目标是修建道路,以便可以通过道路在每对城镇之间旅行。至少需要多少钱才能实现这个目标?
约束
- 2 ≤ N ≤ 10^5
- 0 ≤ x_i,y_i ≤ 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N x_1 y_1 x_2 y_2 : x_N y_N
输出
打印修建道路所需的最低金额,以便可以通过道路在每对城镇之间行驶。
示例输入 1
3 1 5 3 9 7 8
示例输出 1
3
在城镇之间修建道路 1 和 2,以及城镇之间的另一个 2 和 3。总成本是 2+1=3 日元。
示例输入 2
6 8 3 4 9 12 19 18 1 13 5 7 6
示例输出 2
8