P3416 [USACO16DEC] Moocast S

题目描述

约翰农场主的 $N$ 头奶牛想建立一个紧急情况下的“哞哞广播”系统，这样它们就可以在自己中间广播重要信息。

奶牛们想让每头牛装备上一个对讲机，而不是在长距离中向另一头奶牛“哞哞”乱叫。这些对讲机每台都有各自的有效传输半径——一个拥有 $P$ 能量的对讲机只能向距离在 $P$ 以内的牛发送信息（注意可能出现 $A$ 牛对讲机的能量比 $B$ 牛的大，而 $A$ 牛可以给 $B$ 牛发送信息，但 $B$ 牛不能传回信息）。幸运的是，奶牛们可以通过其他奶牛中继，沿着一条跳跃的路径传递信息，因此每个奶牛不必要直接向每个其他奶牛传播。

由于对讲机的费堆成性质，来自一些奶牛的广播可能比其他奶牛的广播能够达到更多的接受者（考虑中继的情况）的能力更有效。请帮助奶牛确定来自单个奶牛的广播可以达到的奶牛的最大数量。

输入格式

第一行，一个整数 $N$。

接下来 $N$ 行，第 $i$ 行包括第 $i$ 只牛的坐标 $(x_i,y_i)$，以及这只牛所持有对讲机的能量 $P_i$。

输出格式

一行，一个整数，表示从来自单个奶牛的广播可以达到的奶牛的最大数量。开始的牛也包括在这个数量中。

输入输出样例 1

4
1 3 5
5 4 3
7 2 1
6 1 1

3

说明/提示

对于 $100\%$ 的数据，$N\le200$，$\forall i \in [1,N]$，$0\le x_i,y_i\le25000$。