TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6091
  • 問題
  • P6091nodgd跳
    制限 : 時間制限 : 10000 MS   メモリ制限 : 262144 KB
    審判説明 : 1s,256MB
    問題説明

    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}$