P6954: 广播系统
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
农夫约翰的N头奶牛(1≤N≤200)想组织一个紧急“哞哞”系统，以便在它们之间广播重要信息。
这些奶牛决定给自己配备对讲机，每头牛一部，而不是长距离的互相哞哞叫。这些对讲机各自具有一个有限的传输半径,功率为P的对讲机只能传输到距离为P的其他奶牛(奶牛A的功率大于奶牛B的功率，即使奶牛B无法回传，奶牛A也可以传输到奶牛B)。幸运的是,奶牛可以沿着由几个牛组成的路径相互传递信息，因此不需要每只奶牛都能直接向其他奶牛发送信息。
由于对讲机传输的不对称特性，一些奶牛发出的广播可能比其他奶牛发出的广播更能有效地传递给大量的接收者(考虑到转播)。请帮助奶牛们确定从一头奶牛发出的广播所能达到的最大奶牛数量。
【输入格式】(moocast.in):
第一行输入包含N。
接下来的N行每一行都包含一头牛的x和y坐标(范围为0…25,000的整数)，然后是p，即奶牛手持对讲机的功率。
【输出格式】(moocast.out):
输出一行，其中包含从单个奶牛发出的广播可以到达的最大奶牛数量。原始奶牛包括在这个数字中。
【样例输入】:
4
1 3 5
5 4 3
7 2 1
6 1 1
样例输出:
3
【样例说明】
在上面的例子中，从奶牛1发出的广播总共可以到达3头奶牛，包括奶牛1。