ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1583. Сыр

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Plus il y a de fromage, plus il y a de trous
or plus il y a de trous, moins il y a de fromage
donc plus il y a de fromage, moins il y a de fromage
Paradoxe de l'emmental
Саша этим летом катался на горных лыжах в швейцарских Альпах. Швейцария знаменита своими банками и своим сыром. Банки Сашу не заинтересовали, но зато он побывал на сыроваренном заводе. Оказалось, что истинный швейцарец к сыру относится еще серьезнее, чем к деньгам. Вот, например, они пакуют сыр в вакуумную упаковку кусками ровно по 500 граммов. Но если вы думаете, что отрезать такие кусочки легко, то вы сильно ошибаетесь: ведь в швейцарском сыре, есть дырки, и немаленькие. К счастью, современные технологии позволяют точно определять размеры и положение всех полостей в сыре.
Сыр подается на станок в виде длинного бруска квадратного сечения, размером 10×10 см и длиной 1 метр. Будем считать, что все полости имеют сферическую форму и не пересекаются друг с другом и краями бруска. Станок умеет делать разрезы строго поперек бруска по микрометровой шкале (то есть по сетке с шагом в 1 мкм). Специальный компьютер находит, где нужно сделать очередной разрез, чтобы вес полученного куска составлял ровно 500 граммов. Значение этой отметки округляется до микрометров, и станок делает соответствующий разрез. После этого компьютер вычисляет, где нужно делать следующий разрез, и так далее, пока вес оставшейся части не будет составлять меньше 500 граммов. Если получится, что очередной разрез нужно сделать на отметке ровно в метр, то, естественно, такой разрез производиться не будет.
Попробуйте и вы написать программу, которая найдет координаты разрезов, такие же, какие нашел бы этот специальный компьютер.

Исходные данные

В первой строке записано число n — количество дырок в сыре (0 ≤ n ≤ 100). В следующих n строках записаны данные о дырках в формате xi yi zi ri, где (xi, yi, zi) — координаты центра дырки, ri — радиус дырки. Брусок имеет размеры 10×100×10 соответственно по осям x, y и z. Координаты отсчитываются от одного из углов бруска и заданы в сантиметрах. Известно, что 1 см3 качественного швейцарского сыра весит ровно 1 грамм.

Результат

Требуется вывести координаты разрезов поперек бруска в значениях шкалы станка. В первой строке выведите количество разрезов. В следующих строках — координаты разрезов в микрометрах от начала бруска.

Пример

исходные данныерезультат
2
3.2 37.2 1.8 1
4.2 66.6 5.5 2.5
19
50000
100000
150000
200000
250000
300000
350000
400419
450419
500419
550419
600419
651114
706964
756964
806964
856964
906964
956964
Автор задачи: Александр Мироненко (подготовил Денис Мусин)
Источник задачи: ACM ICPC 2007–2008. NEERC. Восточный подрегион. Екатеринбург, 27 октября 2007 г.