#P3428. [POI2005] AKC-Special Forces Manoeuvres

[POI2005] AKC-Special Forces Manoeuvres

题目描述

一个秘密组织正在沙漠中举行一次军事演习。本次演习的目标是拆除隐藏在沙漠中的一个炸弹。

演习的第一部分是空降作战。每个士兵按照一定的顺序从悬停在沙漠上空的直升机上跳下。着陆时,每个士兵都会停在他所在的着陆点。

每个空降兵都有一个生存半径。如果炸弹与他的距离小于或等于这个生存半径的话,空降兵便会牺牲自己引爆炸弹。指挥官希望能派出尽可能少的士兵,但他希望在最坏情况下至少有一个士兵能够生还。

整个沙漠可以抽象为一个平面,每个士兵的着陆点可以用一个坐标 (x,y)(x,y) 表示,他的生存半径我们设为 rr。所有士兵的信息按照他们跳伞时的顺序给出,即第 ii 个士兵跳伞时,前 i1i-1 个士兵都已经着陆。

你的任务是:从标准输入读入所有士兵的信息,输出最少需要派出的士兵数量。

输入格式

第一行一个整数 nn

接下来 nn 行,第 ii 行包含三个整数 xi,yi,rix_i,y_i,r_i,代表第 ii 个士兵的着陆坐标为 (xi,yi)(x_i,y_i),生存半径为 rir_i

输出格式

如果无法让至少一个士兵生还的话,输出 NIE

否则输出一个整数,代表至少需要派出的士兵数量。

5
2 2 4
7 2 3
4 3 1
5 7 1
8 7 1
4

提示

最坏情况下炸弹位于 (5,3)(5,3),前三个士兵都会被炸死,第四个士兵会生还。