| History of OI -> XII OI 2004/2005 -> Problems |  |
Task: Special Forces Manoeuvres
Secretly Organized Tactical Infantry Exercises (SORTIE) take place in the Błędowska 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.
Input
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.
Output
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.
Example
For the input data:5 2 2 4 7 2 3 4 3 1 5 7 1 8 7 1the correct outcome is:
4
Attention!
This task may be solved using floating point types:- double or extended in Pascal,
- double or long double in C and C++.
Print friendly version