P6091nodgd跳 | ||
|
問題説明
nodgd琴棋书画都已经精通却毫无用武之地,气的nodgd直跳,于是他出了一道跳的题。
nodgd身处蛮荒之地。蛮荒之地有$n$个安全区,每个安全区在有一个三维空间中的坐标$(x_i,y_i,z_i)$。只要你的跳跃能力足够强,就可以从任意一个安全区直接跳到另外任意一个安全区。确切的说,从$(x_i,y_i,z_i)$跳到$(x_j,y_j,z_j)$需要的跳跃能力是$\min(|x_i-x_j|,|y_i-y_j|,|z_i-z_j|)$。显然,从安全区$i$跳到安全区$j$所需的跳跃能力和反向跳回去所需的跳跃能力是相同的。
nodgd的跳跃能力为$f$,请你帮忙计算有多少组安全区$i,j(i<j)$,它们可以相互到达。如果可以从安全区$i$经过若干次跳跃到达安全区$j$,就认为安全区$i,j$可以相互到达。
入力形式
第一行一个整数$n$。
接下来$n$行,每行三个整数$x_i,y_i,z_i$,表示第$i$个安全区的三维坐标。
最后一行一个整数$f$,表示nodgd的跳跃能力。
出力形式
输出一个整数,表示有多少组安全区可以相互到达。
サンプル入力 1
4
1 1 1
2 2 2
4 4 8
8 8 4
2
サンプル出力 1
6
サンプル入力 2
4
1 20 14
6 3 20
9 12 2
20 18 7
4
サンプル出力 2
2
ヒント
样例说明1
每个安全区都可以跳到第$2$个安全区,所以任意两个安全区都可以相互到达。
样例说明2
安全区$1,4$可以相互到达,因为它们的$y$坐标相差不超过$4$;安全区$2,3$可以相互到达,因为它们$x$坐标相差不超过$4$。
数据规模与约定
$1\leq n\leq 10^{5}, 0\leq x_i,y_i,z_i,f\leq10^{9}$