#Psmt19. 5.最小距离和

5.最小距离和

5.最小距离和

题目描述

有n个点,任意两点A,B的距离(A,B)=MIN{|XA-XB|,|YA-YB|,|ZA-ZB|}。

其中(XA,YA,ZA)是A的空间位置,而(XB,YB,ZB)是B的空间位置。现在需要建立n-1条道路,以使所有点直接或间接相通,并且使所建道路距离和最小。

输入格式

第一行:一个数整数代表点数。

第二行到n+1行:每行三个整数x,y,z,代表点的坐标。

不会出现重复的点。

输出格式

输出一个整数,表示最小距离。

数据范围

(原站未提供,导入后需人工补齐)

样例

3
-1 -1 -1
5 5 5
10 10 10
11

提示

对于50%的数据,保证n<=4000;

对于100%的数据,保证n<=100000,坐标在−109和109-10^9和10^9之间。