构造树——高级
1 Sec 64 MB |
0 | 3 |
通过 | 提交 |
题目描述
有一系列的点,满足任意两个点编号i yj。现在为了把这些点连起来,我们需要构建一颗有向的树,树的边都是向右或者向上,即沿着x轴或者沿着y轴。
下面就是一个样例。
写一个程序,找到可以连接所有点的树,是的树的所有边长度之和最小。
输入格式
第一行一个整数n (1 <= n <= 1000)表示点的个数。
接下来n行,每行两个整数xi,yi(0 <= xi, yi <= 10000)表示第i个点的坐标,且符合题目描述的要求。
输出格式
输出可以连接所有点的树的边之和的最小长度。
样例输入 #1
5 1 5 2 4 3 3 4 2 5 1 1 10000 0
样例输出 #1
12 0