Robots' Crash

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem H: Robot's Crash

Prof. Jenifer A. Gibson is carrying out experiments with many robots. Since those robots are expensive, she wants to avoid their crashes during her experiments at her all effort. So she asked you, her assistant, as follows.

gSuppose that we have n (2 ≤ n ≤ 100000) robots of the circular shape with the radius of r, and that they are placed on the xy-plane without overlaps. Each robot starts to move straight with a velocity of either v or -v simultaneously, say, at the time of zero. The robots keep their moving infinitely unless I stop them. Ifd like to know in advance if some robots will crash each other. The robots crash when their centers get closer than the distance of 2r. Ifd also like to know the time of the first crash, if any, so I can stop the robots before the crash. Well, could you please write a program for this purpose?h


The input consists of multiple datasets. Each dataset has the following format:

vx vy
rx1 ry1 u1
rx2 ry2 u2
rxn ryn un

n is the number of robots. (vx, vy) denotes the vector of the velocity v. r is the radius of the robots. (rxi , ryi ) denotes the coordinates of the center of the i-th robot. ui denotes the moving direction of the i-th robot, where 1 indicates the i-th robot moves with the velocity (vx , vy), and -1 indicates (-vx , -vy).

All the coordinates range from -1200 to 1200. Both vx and vy range from -1 to 1.

You may assume all the following hold for any pair of robots:

  • they must not be placed closer than the distance of (2r + 10-8 ) at the initial state;
  • they must get closer than the distance of (2r - 10-8 ) if they crash each other at some point of time; and
  • they must not get closer than the distance of (2r + 10-8 ) if they donft crash.

The input is terminated by a line that contains a zero. This should not be processed.


For each dataset, print the first crash time in a line, or gSAFEh if no pair of robots crashes each other. Each crash time should be given as a decimal with an arbitrary number of fractional digits, and with an absolute error of at most 10-4.

Sample Input

1.0 0.0
0.0 0.0 1
2.0 0.0 -1
1.0 0.0
0.0 0.0 -1
2.0 0.0 1

Output for the Sample Input


Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest 2007, 2007-10-21