Description
农场主约翰的n头奶牛(1≤n≤200)希望组织一个紧急的“模拟广播”系统,在它们之间广播重要信息。
奶牛们决定给自己配备对讲机,每头奶牛一个对讲机,而不是长距离地相互哞哞叫。这些对讲机都有一个有限的传输半径——功率为P的对讲机只能传输到距离P远的其他奶牛(注意,奶牛A可能能够传输到奶牛B,即使奶牛B不能传输回来,因为奶牛A的功率大于奶牛B的功率)。幸运的是,奶牛可以沿着一条由多个跃点组成的路径相互传递消息,因此没有必要让每头奶牛都能直接向其他奶牛发送消息。
由于对讲机传输的不对称性,一些奶牛的广播可能比其他奶牛更有效,因为它们能够接触到大量的接收者(考虑到中继)。请帮助奶牛确定从一头奶牛发出的广播可以达到的最大奶牛数量。
Input
输入的第一行包含n。
接下来的n行中,每行包含一个奶牛的x和y坐标(0…25000范围内的整数),然后是p,这头奶牛所持对讲机的功率。
Output
写一行输出,其中包含从单个奶牛广播所能达到的最大奶牛数。原始牛包括在这个数字中。
4
1 3 5
5 4 3
7 2 1
6 1 1
HINT
在上面的示例中,Cow1的广播可以达到3头奶牛,包括Cow1。