秘密组织的战术步兵演习(SORTIE)在布莱多夫斯卡沙漠(Bledowska Desert)进行。演习的主要部分是拆除一枚隐藏在沙漠中未知地点的炸弹。
演习的第一部分是空降行动。突击队员们按照预定的顺序,从悬停在沙漠上空的直升机上依次跳伞。着陆后,每名突击队员都会就地挖掘掩体并停止移动,只有在上一名队员完成后,下一名队员才会行动。
每名突击队员都有一个生存半径。如果突击队员与炸弹之间的距离小于或等于该生存半径,那么一旦炸弹爆炸,该突击队员就会牺牲。指挥部希望在确保至少有一名突击队员在可能的爆炸中幸存的前提下,使参与行动的士兵人数最少。
我们假设布莱多夫斯卡沙漠是一个平面,并将突击队员挖掘掩体后的位置视为该平面上的点。我们已知突击队员跳伞的顺序。没有人可以跳过自己的轮次,即如果第 $i$ 名突击队员从直升机上跳下,那么在他之前的所有队员都必须已经跳下。对于每一名突击队员,我们已知其生存半径以及他如果被要求跳伞时将着陆的坐标。
请编写一个程序,完成以下任务:
- 从标准输入读取每名突击队员的描述;
- 计算需要跳伞的最少突击队员人数;
- 将结果写入标准输出。
输入格式
标准输入的第一行包含一个整数 $n$ ($2 \le n \le 2\,000$),表示突击队员的人数。接下来的 $n$ 行包含突击队员的描述,每行一个。每名突击队员的描述由三个整数组成:$x$、$y$ 和 $r$ ($-1\,000 \le x, y \le 1\,000$, $1 \le r \le 5\,000$)。点 $(x, y)$ 表示突击队员的着陆位置,$r$ 表示其生存半径。如果突击队员发现自己处于距离炸弹 $r$ 的生存半径内,那么一旦炸弹爆炸,他就会牺牲。
输出格式
在标准输出的第一行(也是唯一一行)中,输出一个整数,表示为了确保至少有一人幸存所需跳伞的最少突击队员人数;如果无法绝对保证其中一人幸存,则输出单词 NIE(波兰语中的“不”)。
样例
样例输入 1
5 2 2 4 7 2 3 4 3 1 5 7 1 8 7 1
样例输出 1
4
说明
本题可以使用浮点类型求解:
- Pascal 中的
double或extended; - C 和 C++ 中的
double或long double。
使用 float 或 real 类型可能会因浮点运算误差导致结果不正确。