8749: BZOJ4749：[Usaco2016 Dec]Moocast

Farmer John's N cows (1≤N≤200) want to organize an emergency "moo-cast" system for broadcasting im portant messages among themselves.Instead of mooing at each-other over long distances, the cows deci de to equip themselves with walkie-talkies, one for each cow. These walkie-talkies each have a limit ed transmission radius -- a walkie-talkie of power PP can only transmit to other cows up to a distan ce of PP away (note that cow A might be able to transmit to cow B even if cow B cannot transmit back , due to cow A's power being larger than that of cow B). Fortunately, cows can relay messages to one -another along a path consisting of several hops, so it is not necessary for every cow to be able to  transmit directly to every other cow.Due to the asymmetrical nature of the walkie-talkie transmissi on, broadcasts from some cows may be more effective than from other cows in their ability to reach l arge numbers of recipients (taking relaying into account). Please help the cows determine the maximu m number of cows that can be reached by a broadcast originating from a single cow. 每头牛手上有一台对讲机，给出N（1≤N≤200）头牛的坐标（X,Y）及其对讲机的极限传输半径P，也就是说该对讲 机能将信息传送到与之距离不超过P的对讲机。幸运的是,牛可以传递消息通过其他牛，所以没有必要每头牛能直接 传送到其他牛。请帮助奶牛确定：如果源于一头牛，最多能将信息传递到多少头牛？

输入格式

The first line of input contains N.The next N lines each contain the xx and yy coordinates of a sing le cow ( integers in the range 0…25,000) followed by p, the power of the walkie-talkie held by this  cow.

输出格式

Write a single line of output containing the maximum number of cows a broadcast from a single cow ca n reach. The originating cow is included in this number.

样例输入

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

样例输出

3
In the example above, a broadcast from cow 1 can reach 3 total cows, including cow 1.

提示

没有写明提示

题目来源

Silver 鸣谢winmt提供译文