AT_abc257_d [ABC257D] Jumping Takahashi 2

题目描述

高桥君居住的二维平面上的城市中有 $N$ 个跳板。第 $i$ 个跳板位于点 $(x_i, y_i)$，该跳板的力量为 $P_i$。高桥君的跳跃力用 $S$ 表示，初始时 $S=0$。每当高桥君进行一次训练，$S$ 就会增加 $1$。

只有在满足以下条件时，高桥君才能从第 $i$ 个跳板跳到第 $j$ 个跳板：

• $P_i S \geq |x_i - x_j| + |y_i - y_j|$

高桥君的目标是，选择一个合适的跳板作为起点，使得从该跳板出发，可以通过若干次跳跃到达任意一个跳板。

为了实现这个目标，高桥君最少需要进行多少次训练？

输入格式

输入以如下格式从标准输入读入。

$N$
$x_1$ $y_1$ $P_1$
$\vdots$
$x_N$ $y_N$ $P_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #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

说明/提示

限制条件

• $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)$
• 所有输入均为整数

样例解释 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|$。）

由 ChatGPT 4.1 翻译