← 返回题目列表

Codeforces · 1619/G

G. 不寻常的扫雷

中文机器翻译题面 查看原题

波利卡普非常喜欢玩扫雷游戏。最近他发现了一个类似的游戏,还有这样的规则。

场地上有地雷,每个地雷的位置坐标都是已知的($$$x_i, y_i$$$)。每个地雷都有几秒钟的寿命,之后就会爆炸。爆炸后,地雷还会引爆距离$$$k$$$(两条垂直线)垂直和水平方向上的所有地雷。结果,我们在场上看到了“加号”符号(“+”)形式的爆炸。因此,一次爆炸可能会引起新的爆炸,依此类推。

此外,波利卡普每秒都可以引爆任何人的地雷,从零秒开始。之后,还会发生爆炸的连锁反应。根据上述规则,地雷立即爆炸,并立即引爆其他地雷。

波利卡普想要创造新的记录,请你帮他计算最少需要多少秒才能引爆所有地雷。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。

每个测试套件前面都写有一个空行。

接下来是一行,包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$) — 分别是地雷数量和爆炸期间被地雷击中的距离。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 行描述了第 $$$i$$$ 地雷的 $$$x$$$ 和 $$$y$$$ 坐标以及爆炸之前的时间 ($$$-10^9 \le x, y \le 10^9$$$, $$$0 \le timer \le 10^9$$$)。保证所有地雷都有不同的坐标。

保证测试中所有测试用例的值 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

打印 $$$t$$$ 行,每行必须包含相应输入数据集的答案 - 引爆所有地雷所需的最少秒数。

示例

输入 #1

3

5 0
0 0 1
0 1 4
1 0 2
1 1 3
2 2 9

5 2
0 0 1
0 1 4
1 0 2
1 1 3
2 2 9

6 1
1 -1 3
0 -1 9
0 1 7
-1 0 1
-1 1 9
-1 -1 7

输出 #1

2
1
0

注意

示例图片

第一个例子:

- $$$0$$$ 第二:我们在 $$$(2, 2)$$$ 单元格引爆了一个地雷,因为 $$$k=0$$$,它不会引爆任何其他地雷。
- $$$1$$$ 第二:我们引爆单元格 $$$(0, 1)$$$ 处的地雷,单元格 $$$(0, 0)$$$ 处的地雷会自行爆炸。
- $$$2$$$ 第二:我们引爆炸了单元格 $$$(1, 1)$$$ 处的地雷,单元格 $$$(1, 0)$$$ 处的地雷自行爆炸。

第二个例子:

- $$$0$$$ 第二:我们在 $$$(2, 2)$$$ 单元格引爆地雷,我们得到:

- $$$1$$$ 第二个:坐标 $$$(0, 0)$$$ 处的地雷爆炸,由于 $$$k=2$$$,爆炸引爆了单元格 $$$(0, 1)$$$ 和 $$$(1, 0)$$$ 处的地雷,它们的爆炸引爆了单元格 $$$(1, 1)$$$ 处的地雷,并且没有留下任何地雷在球场上。