题目详情题解（0）讨论（0）提交记录（0）

AT_abc257_d.[ABC257D] Jumping Takahashi 2

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

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

  • PiS≥∣xi−xj∣+∣yi−yj∣P_i S \geq |x_i - x_j| + |y_i - y_j|

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

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

输入格式

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

NN
x1x_1 y1y_1 P1P_1
⋮\vdots
xNx_N yNy_N PNP_N

输出格式

请输出答案。

输入输出样例

  • 输入#1

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

    输出#1

    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≤N≤2002 \leq N \leq 200
  • −109≤xi,yi≤109-10^9 \leq x_i, y_i \leq 10^9
  • 1≤Pi≤1091 \leq P_i \leq 10^9
  • (xi,yi)≠(xj,yj) (i≠j)(x_i, y_i) \neq (x_j, y_j)\ (i \neq j)
  • 所有输入均为整数

样例解释 1

如果高桥君进行了 22 次训练，即 S=2S=2，那么可以从第 22 个跳板出发，到达所有跳板。例如，到达第 44 个跳板的方法如下：

  • 从第 22 个跳板跳到第 33 个跳板。（P2S=10P_2 S = 10，∣x2−x3∣+∣y2−y3∣=10|x_2-x_3| + |y_2-y_3| = 10，满足 P2S≥∣x2−x3∣+∣y2−y3∣P_2 S \geq |x_2-x_3| + |y_2-y_3|。）
  • 从第 33 个跳板跳到第 44 个跳板。（P3S=2P_3 S = 2，∣x3−x4∣+∣y3−y4∣=1|x_3-x_4| + |y_3-y_4| = 1，满足 P3S≥∣x3−x4∣+∣y3−y4∣P_3 S \geq |x_3-x_4| + |y_3-y_4|。）

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页