ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC 2008, Eastern subregion quarterfinals

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Somali Pirates

Time limit: 1.0 second
Memory limit: 64 MB
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 same position.
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
To submit the solution for this problem go to the Problem set: 1655. Somali Pirates