Jumping Takahashi 2

题目描述

Takahashi 居住的二维平面城镇上有 $N$ 个蹦床。第 $i$ 个蹦床位于点 $(x_i, y_i)$，并且具有能力值 $P_i$。Takahashi 的跳跃能力记为 $S$。最初，$S=0$。每当 Takahashi 训练一次，$S$ 增加 $1$。 当且仅当满足下列不等式时，Takahashi 可以从第 $i$ 个蹦床跳到第 $j$ 个蹦床：

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

Takahashi 的目标是通过训练使得他能够选择一个起始蹦床，从该蹦床出发通过若干次跳跃到达任意一个蹦床。 他至少需要训练多少次以实现该目标？

输入格式

输入由标准输入按以下格式提供： $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

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 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)$ 输入中的所有值均为整数。如果他训练两次，$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|$。）

标签: AtCoder|abc257D

来源

AtCoder|abc257D