← 返回题目列表

AtCoder · abc257_d

G. 跳跃的高桥 2

中文机器翻译题面 查看原题

分数: 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