2D Solar System
Time limit1sMemory limit128 MB
Circles tangent to one straight line glide with constant velocity, and the program reports when the first two touch.
- Level
Hard8 of 10
- Topics
- Geometry, Sorting, Heap, Simulation
- Solved
- No attempts yet
Problem
The 2D solar system looks much like ours: it has a sun called Bigsun and many circular planets that orbit it. Bigsun's gravity is so strong that every planet has been pulled onto it. Each planet orbits Bigsun while staying tangent to it, as in the figure below. Bigsun is so huge that its boundary looks like a straight line.
No two planets have collided so far, but nobody knows whether the system stays free of collisions. Write a program that decides whether a collision can happen in the future and, if one can, computes the time of the first collision.
Scientists at NASA found that every planet in the 2D solar system moves at a constant velocity. The motion of a planet is described by the position of the point where it touches Bigsun's boundary. At time that position is , where and are two values given for the planet.
All planets touch Bigsun's boundary on the same side. Two planets collide the moment they touch.

Input
The input holds several test cases. Each test case starts with a line containing the number of planets (). The -th of the next lines contains three integers , , separated by spaces, and none of them exceeds 1,000,000,000 in absolute value. is a positive square number and is the radius of planet . and fix the motion equation, so at time the point where planet touches Bigsun's boundary sits at .
The input ends with a line containing a single , which you must not process.
Output
For each test case, print the time of the first collision on its own line. The current time is , and at the current time all planets are pairwise disjoint. If the system is free of collisions, print Collision-Free System.
Print the time rounded to exactly two digits after the decimal point. A value that falls exactly halfway rounds up.