2D-Сонячна система
Сонячна система 2D, подібна до нашої, складається з Великого Сонця та його планетарної системи, що включає багато круглих планет, які обертаються навколо Великого Сонця. Через високу гравітацію всі планети притягуються до нього. Вони обертаються навколо Великого Сонця, торкаючись його, як показано на рисунку (оскільки Велике Сонце таке величезне, його межа виглядає як лінія). Дивно, але до цього часу жодна з планет не зіткнулася одна з одною, але ніхто не знає, чи залишиться система вільною від зіткнень у майбутньому. Вам потрібно написати програму, щоб перевірити, чи можливе зіткнення в майбутньому, і якщо так, обчислити час, коли відбудеться перше зіткнення. Вчені NASA з'ясували, що кожна планета в сонячній системі 2D рухається з постійною швидкістю. Точніше, положення точки дотику планети з межею Великого Сонця через час описується лінійним рівнянням y = at + b, де a і b — відомі параметри, а t позначає час.
Вхідні дані
Вхід містить кілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить ціле число n (0 ≤ n ≤ 50000), де n — кількість планет. i-й рядок з наступних n рядків містить 3 цілі числа, розділені пробілами: r_i, a_i та b_i, абсолютні значення яких не перевищують 1000000000. Число r_i, яке є позитивним квадратом, позначає радіус планети i, а a_i та b_i визначають її рівняння руху, тобто положення точки дотику планети на межі Великого Сонця в момент часу t є a_it + b_i. Вхід завершується рядком, що містить "0", який не слід обробляти.
Вихідні дані
Для кожного тестового випадку виведіть рядок, що містить час, коли відбудеться перше зіткнення, за умови, що поточний час дорівнює 0 і всі планети не перетинаються в поточний час. Якщо система вільна від зіткнень, ви повинні вивести "Collision-Free System". Вихід має бути округлений до двох знаків після коми.