Задача №112550. Интервалы
В подвале вновь построенного здания на потолке расположен сильный источник света. К сожалению, покрытие на полу очень чувствительно к свету и разрушается под его воздействием. Чтобы этого избежать было решено защитить покрытие от света, однако сделать это не легко, т.к. в подвале проходит много труб и если они уже загораживают часть пола от света, то соответствующие участки было решено дополнительно не защищать.
Поиск решения можно проводить с помощью двухмерной модели. В этой модели ось Ох расположена на уровне пола, источник света считается точкой с целочисленными координатами ( b x , b y ) . Трубы представляют собой окружности. Центр i -й окружности имеет целочисленные координаты ( с x , c y ) , радиус r i также целый. Так как трубы сделаны из твердого материала, окружности не пересекаются. Трубы не отражают и не пропускают свет. Вы должны написать программу, которая найдет непересекающиеся интервалы на оси Ох , которые уже защищены от света благодаря имеющимся трубам.
Входной файл состоит из набора сразу нескольких тестов. Общее число строк в файле не превосходит 20000 . В первой строке каждого теста содержится положительное целое число N ≤ 10000 — обозначающее количество труб. Во второй строке расположены два целых числа b x и b y , разделенных пробелом. Каждая из следующих N строк содержит 3 целых числа через пробел с x , c y и r i , причем c y + r i < b y . Последний тест содержит единственную строку, содержащую N = 0 .
Для каждого теста выведите набор искомых интервалов по одному в строке. Интервал описывается двумя вещественными координатами. Ответ будет считаться правильным, если его относительная и абсолютная погрешности не будут превосходить \(10^{-6}\). Интервалы должны быть отсортированы в порядке возрастания координаты x . В конце каждого набора интервалов выводите пустую строчку.
Картинки иллюстрируют тест из условия.
1 300 300 300 150 90 6 300 450 70 50 30 120 20 20 270 40 10 250 85 20 220 30 30 380 100 100 0
75.00 525.00 0.72 78.86 88.50 133.94 181.04 549.93