eolymp
bolt
Try our new interface for solving problems
Problems

2D-Solar System

2D-Solar System

The \textbf{2D}-solar system like our solar system comprises Bigsun (its sun) and its planetary system of many circular planets orbiting around Bigsun. Due to the high gravity of Bigsun, all planets have been attracted by Bigsun. Precisely, they orbit around Bigsun while being tangent to it as depicted in the figure (As Bigsun is so huge, its boundary looks like aline.) Surprisingly, up to the current time no two planets have collided with each other, but no one knows whether the system is free of collisions in the future. You are to write a program to verify whether there is a possibility of any collision in the future and if so, compute the time at which the first collision happens. The scientists of NASA have realized that each planet in the \textbf{2D}-solar system moves with a constant velocity. More precisely, it turned out that the motion equation of a planet can be described by the position of its touching point with the boundary of Bigsun through time by the linear equation \textbf{y = at + b} where \textbf{a} and \textbf{b} are two known parameters and \textbf{t} denotes time. \includegraphics{https://static.e-olymp.com/content/98/9858733ad8686ef14c238bac3d1d79e6cc813974.jpg} \InputFile There are multiple test cases in the input. Each test case starts with a line containing an integer \textbf{n} (\textbf{0} ≤ \textbf{n} ≤ \textbf{50000}) where \textbf{n} is the number of planets. The \textbf{i}^th line of the next \textbf{n} lines contains \textbf{3} space-separated integers \textbf{r_i}, \textbf{a_i}, and \textbf{b_i}whose absolute values are not exceeding \textbf{1000000000}. The number \textbf{r_i} which is a positive square number, denotes the radius of Planet \textbf{i} and \textbf{a_i} and \textbf{b_i} specify its motion equation, i.e. the position of the tangent point of the planet on the boundary of Bigsun at time \textbf{t} is \textbf{a_it + b_i}. The input terminates with a line containing "\textbf{0}" which should not be processed. \OutputFile For each test case, output a line containing the time at which the first collision happens under the assumption that the current time is equal to \textbf{0} and all planets are disjoint at the current time. If the system is free of collisions you must output "\textbf{Collision-Free System}". The output must be rounded to exactly two digits after the decimal point.
Time limit 1 second
Memory limit 64 MiB
Input example #1
3
1 1 1
4 3 6
9 -7 30
2
4 -1 1
1 1 7
2
1 1 10
1 2 5
0
Output example #1
1.20
Collision-Free System
3.00
Source 38th ACM International Collegiate Programming Contest, 2013–2014 Asia Region, Tehran Site, Sharif University of Technology, 19–20 December 2013