0 人解决，0 人已尝试。
0 份提交通过，共有 0 份提交。
9.9 EMB 奖励。
1403. Special Forces Manoeuvres
单点时限: 2.0 sec
内存限制: 256 MB
Secretly Organized Tactical Infantry Exercises (SORTIE) take place in the Bdowska Desert. The main part of the SORTIE shall be the disarmament of a bomb, hidden in an unknown location in the desert.
The first part of the manoeuvres is an airborne operation. The commandos jump individually, in a predetermined order, from a helicopter hovering above the desert. Upon landing, each commando digs in and moves no further. Only then does the next commando proceed.
There is a survival radius defined for each commando. If the distance between the commando and the bomb is equal to (or smaller then) the survival radius, the commando will perish should the bomb go off. The command wants to minimize the number of soldiers taking part in the operation, but it wants to be sure that at least one of them survives the possible explosion.
We shall assume for our purposes that the Błędowska Desert is a plain and we shall identify the positions of the dug in commandos with points on this plane. We are given a sequence of commandos to jump. None of them may miss his turn, i.e. if the i-th commando jumps from the helicopter, than all those before him have already jumped. For each of the commandos we know his survival radius and the coordinates of the point he is going to land in, should he be required to jump.
Task
Write a programme which:
reads from the standard input a description of each commando,
calculates the minimal number of commandos to jump,
writes the outcome to the standard output.
输入格式
In the first line of the standard input there is a single integer n ( 2 <= n <= 2 000) – the number of commandos. The following n lines contain descriptions of commandos – one per line. The description of each commando is comprised of three integers: x, y and r ( -1000 <= x, y <= 1000, 1 <= r <= 5000). The point (x, y) denotes the landing place of the commando, and r denotes his survival radius. If the commando finds himself within the survival radius r from the bomb, he will perish should the bomb go off.
输出格式
In the first and only line of the standard output your programme should write a single integer - the minimal number of commandos required to jump in order to secure the survival of at least one of them, or a single word NIE (NO in Polish) if it is not possible to have an unconditional certainty that one of the commandos survives.
样例
Input
5 2 2 4 7 2 3 4 3 1 5 7 1 8 7 1
Output
4 Attention! This task may be solved using floating point types: double or extended in Pascal, double or long double in C and C++. The use of float or real types may result in incorrect results due to the floating point arithmetic errors.
题目标签