当前没有测试数据。

D - 跳跃的高橋2

得分：400分

问题描述

高橋所居住的一个二维平面城市中有N个跳床。第i个跳床位于点$(x_i, y_i)$，并有一个强度$P_i$。高橋的跳跃能力用$S$表示。最初，$S=0$。每次高橋训练，$S$增加1。

高橋可以从第i个跳床跳到第j个跳床，当且仅当：

• $P_iS\geq |x_i - x_j| +|y_i - y_j|$。

高橋的目标是能够选择一个起始跳床，以便他可以通过一些跳跃到达任何一个跳床。

他至少需要训练多少次才能达到目标？

约束

• $2 \leq N \leq 200$
• $-10^9 \leq x_i,y_i \leq 10^9$
• $1 \leq P_i \leq 10^9$
• $(x_i, y_i) \neq (x_j,y_j)\ (i\neq j)$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$

$x_1$ $y_1$ $P_1$

$\vdots$

$x_N$ $y_N$ $P_N$

输出

输出答案。

4
-10 0 1
0 0 5
10 0 1
11 0 1

2

如果他训练两次，$S=2$， 在这种情况下，他可以从第2个跳床跳到任意一个跳床。

例如，他可以如下到达第4个跳床。

• 从第2个跳床跳到第3个跳床。（因为$P_2 S = 10$，并且$|x_2-x_3| + |y_2-y_3| = 10$，满足$P_2 S \geq |x_2-x_3| + |y_2-y_3|$。）

• 从第3个跳床跳到第4个跳床。（因为$P_3 S = 2$，并且$|x_3-x_4| + |y_3-y_4| = 1$，满足$P_3 S \geq |x_3-x_4| + |y_3-y_4|$。）

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

18