4080 - 气象监测

题目描述

某气象局在全国部署了 N 个自动气象监测站(编号 1 \sim N),每个监测站都配备有无线信号发射装置。当极端天气发生时,监测站将启动应急通信模式。

i 个监测站的发射装置的有效覆盖半径为 E_i ,只有当第 j 个监测站到第 i 个监测站的距离不超过 E_i 时,第 j 个监测站才能接收到第 i 个监测站发送的数据(注意第 j 个监测站可能无法反向传输)。数据可以通过多个监测站中继传递,例如如果监测站 1 发送的数据能被监测站 2 收到,监测站 2 发送的数据能被监测站 3 收到,那么监测站 1 发送的数据就可以通过监测站 2 传递到监测站 3

气象专家需要评估整个网络的应急能力,请编程计算出:从 N 个监测站中任意选 1监测站发出警报,最多能通知到多少个监测站(包含自身)。

请注意:假设第 i 个监测站位于平面上的 X_i,Y_i 处,第 j 个监测站位于平面上的 X_j,Y_j 处。第 i 个监测站到第 j 个监测站之间的距离,请使用公式 \sqrt{(X_i-X_j)^2 + (Y_i-Y_j)^2} 计算。

输入

第一行输入整数 N 代表监测站的总数。

接下来 N 行,每行包含三个整数 X_i,Y_i,E_i,表示第 i 个监测站位于平面上坐标为 (x_i,y_i) 的位置,其有效覆盖半径为 E_i

输出

输出一个整数,表示最大可通知到的监测站数量。

样例

输入

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

输出

3

输入

12
16 13 4
1 15 3
19 19 7
1 0 3
15 4 4
10 13 4
14 13 1
6 14 5
14 8 0
14 19 8
17 0 5
19 2 4

输出

5

输入

26
24 21 7
23 1 14
43 15 9
9 39 13
45 4 9
24 35 11
22 23 14
17 41 0
16 6 5
3 15 12
17 23 0
10 4 5
4 10 8
26 21 0
20 11 11
36 27 1
10 37 12
22 40 5
12 3 12
9 15 4
43 44 8
2 25 9
1 10 5
11 31 14
36 47 11
17 13 7

输出

21
说明

样例 1 解释

4 个监测站,如果选择监测站 1 或者 2 发出警报,都可以通知到 1 2 33 个监测站。

数据范围

对于所有的测试数据,满足 1 \leq N \leq 2000 \leq X_i,Y_i \leq 250001 \leq E_i \leq 2\times10^4

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 入门


上一题 下一题