7979: Moocast

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:23 通过:12

题目描述

农夫约翰的 N 头奶牛想要建立一个紧急的奶牛广播系统,在它们之间广播重要信息。

奶牛们决定采用对讲机来进行沟通,因此,每头奶牛都需要配备一个对讲机。

每个对讲机都具有有限的信息传输半径----功率为 P 的对讲机只能将信息传送给距离不超过 P 的其他奶牛。

请注意,可能存在奶牛 A 的对讲机功率大于奶牛 B 的对讲机,因而奶牛 A 可以给奶牛 B 传送信息,奶牛 B 却不能给奶牛 A 传送信息的情况。

幸运的是,奶牛们可以通过互相帮忙传话的方式实现远距离沟通,因此,不必使每头奶牛都能与其他奶牛进行直接沟通。

由于对讲机传输的不对称性,不同奶牛发出的信息所能覆盖到的其他奶牛的数量可能不同(考虑信息转发情况)。

请帮助奶牛确定一头奶牛发出的信息最多可以覆盖到多少头奶牛。

输入格式

第一行包含整数 N

接下来 N 行,每行包含三个整数 x,y,p,表示一头奶牛所处的位置坐标为 (x,y),所拿的对讲机的功率为 p

输出格式

输出一头奶牛发出的信息所能覆盖的奶牛最大数量。

自己也视为被自己发出的信息覆盖。

数据范围

1≤N≤200,

0≤x,y≤25000,

1≤p≤10000


Farmer John's NN cows (1≤N≤2001≤N≤200) want to organize an emergency "moo-cast" system for broadcasting important messages among themselves.

Instead of mooing at each-other over long distances, the cows decide to equip themselves with walkie-talkies, one for each cow. These walkie-talkies each have a limited transmission radius -- a walkie-talkie of power PP can only transmit to other cows up to a distance 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 transmission, broadcasts from some cows may be more effective than from other cows in their ability to reach large numbers of recipients (taking relaying into account). Please help the cows determine the maximum number of cows that can be reached by a broadcast originating from a single cow.

INPUT FORMAT (file moocast.in):

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

OUTPUT FORMAT (file moocast.out):

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

SAMPLE INPUT:

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

SAMPLE OUTPUT:

3

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

Problem credits: Brian Dean

输入样例 复制


输出样例 复制