分数: 400 点
问题陈述
有 N 高桥居住的二维平面小镇上的蹦床。 的 i第一个蹦床位于该点 (x_i, y_i) 并具有以下能力 P_i。 高桥的跳跃能力表示为 S。 最初, S=0。 高桥每次训练的时候, S 增加 1.
高桥可以从 i-第 j-th 蹦床当且仅当:
- 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
输出
打印答案。
示例输入 1
4 -10 0 1 0 0 5 10 0 1 11 0 1
示例输出 1
2
如果他训练两次, S=2, 在这种情况下,他可以从 2-第一个。
例如,他可以到达 4第一个蹦床如下。
-
从 2-nd 到 3-rd 蹦床。 (因为 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-rd 到 4-th 蹦床。 (因为 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|.)
示例输入 2
7 20 31 1 13 4 3 -10 -15 2 34 26 5 -2 39 4 0 -50 1 5 -20 2
示例输出 2
18