102573: [AtCoder]ABC257 D - Jumping Takahashi 2

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：37 Solved：4

Description

Score : $400$ points

Problem Statement

There are $N$ trampolines on a two-dimensional planar town where Takahashi lives. The $i$-th trampoline is located at the point $(x_i, y_i)$ and has a power of $P_i$. Takahashi's jumping ability is denoted by $S$. Initially, $S=0$. Every time Takahashi trains, $S$ increases by $1$.

Takahashi can jump from the $i$-th to the $j$-th trampoline if and only if:

  • $P_iS\geq |x_i - x_j| +|y_i - y_j|$.

Takahashi's objective is to become able to choose a starting trampoline such that he can reach any trampoline from the chosen one with some jumps.

At least how many times does he need to train to achieve his objective?

Constraints

  • $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)$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

2

If he trains twice, $S=2$, in which case he can reach any trampoline from the $2$-nd one.

For example, he can reach the $4$-th trampoline as follows.

  • Jump from the $2$-nd to the $3$-rd trampoline. (Since $P_2 S = 10$ and $|x_2-x_3| + |y_2-y_3| = 10$, it holds that $P_2 S \geq |x_2-x_3| + |y_2-y_3|$.)

  • Jump from the $3$-rd to the $4$-th trampoline. (Since $P_3 S = 2$ and $|x_3-x_4| + |y_3-y_4| = 1$, it holds that $P_3 S \geq |x_3-x_4| + |y_3-y_4|$.)

Sample Input 2

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

Sample Output 2

18

Input

题意翻译

给定 $ n $ 个不共点的蹦床，第 $ i $ 个蹦床的位置为 $ (x_i, y_i) $，反弹力为 $ p_i $。存在整数 $ S $。定义能从第 $ i $ 个蹦床跳到第 $ j $ 个蹦床当且仅当 $ p_i \times S \ge \lvert x_i - x_j \rvert + \lvert y_i - y_j \rvert $。你需要钦定一个起点，使得可以从该蹦床抵达所有蹦床（可以多步），并最小化 $ S $，输出最小值。

Output

分数：400分

问题描述

在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的目标是能够选择一个起始蹦床，以便他可以从选择的蹦床上通过一些跳跃到达任何蹦床。

他需要训练至少多少次才能实现他的目标？

约束条件

  • $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个蹦床跳到第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|$。)

样例输入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

Source/Category

加入题单

上一题 下一题 算法标签：