From the news: “Somali pirates seized a Dutch ship with Russians and
Filipinos aboard. The ship was flying the Panama flag and sailing from
Kenya to Romania with a cargo of German oil derricks.”
This time pirates caught sight of the Dutch ship Lightning
carrying the newest laser gun. Of course, they couldn't leave aside
such a valuable cargo. Pirate ships gathered round the Dutch vessel,
but the Russian seamen were not so easy to catch. They started
to shoot the pirate ships using their laser gun. The crew tried not to let
any of the pirate ships come to them closer than one nautical mile,
because otherwise it would be impossible to aim the laser gun at the
target and the pirates would capture the ship.
The laser gun can rotate
in any of the two directions with angular velocity of at most w
rotations per minute. The gun can fire instantaneously, without even
stopping its rotation. A ship on the firing line sinks immediately.
All pirate ships move strictly in the direction of the Lightning. Each of
them has its own constant velocity of vi knots (1 knot is 1
nautical mile per hour). The azimuth of the i-th pirate ship with respect
to the Dutch ship is bi (the azimuth is the clockwise deviation
from North in degrees). All pirate ships have different azimuths.
At the initial moment, the gun is directed along the azimuth a, and
the i-th pirate ship is at a distance of di nautical
miles from the Dutch ship. We assume that the Lightning stays at the
Determine the order in which the Lightning must shoot at the pirate
ships in order to sink them in the minimal time.
The first line contains the numbers a, w, and n
(0 ≤ a < 360; 0.01 ≤ w ≤ 1;
1 ≤ n ≤ 500). In each of the following n lines
you are given the numbers bi, di, and
vi (0 ≤ bi < 360;
1 ≤ di ≤ 1000; 0.01 ≤ vi ≤ 100).
All numbers contain at most three fractional digits.
If the Lightning can sink all pirate ships, then in the first line
output the minimal time necessary for that in minutes accurate to
10-3, and in the following n lines output the order in
which the ships should be shot (the pirate ships are numbered from 1 to
n in the
order in which they are given in the input). Output the only line
“Impossible” if it is impossible to shoot all pirates ships.
0.0 0.05 2
144.0 22.0 100.0
216.0 22.0 100.0
0.0 0.05 2
144.0 20.0 100.0
216.0 20.0 100.0
Problem Author: Denis Musin
Problem Source: NEERC 2008, Eastern subregion quarterfinals