D - Jumping Takahashi 2 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

高橋君が住んでいる二次元平面上の街には N 個のジャンプ台があります。i 番目のジャンプ台は点 (x_i, y_i) にあり、ジャンプ台のパワーは P_i です。また高橋君のジャンプ力は S で表され、はじめ S=0 です。高橋君が訓練を 1 回行う度に S は 1 増えます。

高橋君は以下の条件を満たす場合に限り、i 番目のジャンプ台から j 番目のジャンプ台にジャンプすることができます。

  • 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

高橋君が 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

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