← 返回 google 的题目列表Detonate Bombs with Chain Reactions (Graph reachability)
类型：online_judge
You are given n bombs. Bomb i is described by bombs[i] = [xi, yi, ri], meaning it is located at (xi, yi) with explosion radius ri.
If bomb i is detonated, it will trigger every bomb j whose Euclidean distance to i is <= ri. Triggered bombs may further trigger others (chain reaction).
You may choose exactly one bomb as the initial detonation. Return the maximum number of bombs that can be detonated.
Input
First line: integer n
Next n lines: xi yi ri
Output
Print one integer: the maximum number of bombs that can be detonated.
Constraints
1 <= n <= 1000
-1e5 <= xi, yi <= 1e5
1 <= ri <= 1e5
Use squared distances to avoid floating point:
((xi-xj)^2 + (yi-yj)^2) <= ri^2
Example
Input:
3
2 1 3
6 1 4
4 1 1
Output:
3
Example
Input
2
0 0 1
3 0 1
Output
1