Наследовать сферы
В году 2xxx экспедиционная команда, высадившись на планету, обнаружила странные объекты, созданные древним видом, жившим на этой планете. Это прозрачные коробки, содержащие непрозрачные твердые сферы (Рисунок 1). Также имеется множество литографий, которые, по-видимому, содержат позиции и радиусы сфер.
Рисунок 1. Странный объект
Изначально их назначение было неизвестно, но профессор Замбендорф обнаружил, что сечение, образованное горизонтальной плоскостью, играет важную роль. Например, сечение объекта изменяется, как на Рисунке 2, при перемещении плоскости снизу вверх.
Рисунок 2. Сечения на разных уровнях
В конце концов он обнаружил, что некоторая информация выражается переходами числа связанных фигур в сечении, где каждая связанная фигура является объединением дисков, пересекающихся или касающихся друг друга, и каждый диск является сечением соответствующей твердой сферы. Например, на Рисунке 2, чья геометрия описана в первом образце данных позже, число связанных фигур изменяется как 0, 1, 2, 1, 2, 3, 2, 1, и 0, при z = 0.0000, 162.0000, 167.0000, 173.0004, 185.0000, 191.9996, 198.0000, 203.0000, и 205.0000, соответственно. Присваивая 1 для увеличения и 0 для уменьшения, переходы этой последовательности могут быть выражены 8-битным двоичным числом 11011000.
Для помощи в дальнейшем анализе напишите программу, чтобы определить переходы при перемещении горизонтальной плоскости снизу (z = 0) вверх (z = 36000).
Входные данные
Входные данные состоят из серии наборов данных. Каждый набор данных начинается с строки, содержащей положительное целое число, которое указывает количество сфер N в наборе данных. За ним следуют N строк, описывающих центры и радиусы сфер. Каждая из N строк содержит четыре положительных целых числа X_i, Y_i, Z_i и R_i (i = 1, ..., N), описывающих центр и радиус i-й сферы соответственно.
Вы можете предположить, что 1 ≤ N ≤ 100, 1 ≤ R_i ≤ 2000, 0 < X_i - R_i < X_i + R_i < 4000, 0 < Y_i - R_i < Y_i + R_i < 16000, и 0 <Z_i - R_i < Z_i + R_i < 36000. Каждая твердая сфера определяется как множество всех точек (x, y, z), удовлетворяющих (x - X_i)^2 + (y - Y_i)^2+ (z - Z_i)^2 ≤ R_i^2.
Сфера может содержать другие сферы. Ни две сферы не касаются друг друга. Каждое Z_i ± R_i и минимальные/максимальные z координаты круга, образованного пересечением любых двух сфер, отличаются друг от друга как минимум на 0.01.
Конец входных данных обозначается строкой с одним нулем.
Выходные данные
Для каждого набора данных ваша программа должна выводить две строки. Первая строка должна содержать целое число M, указывающее количество переходов. Вторая строка должна содержать M-битное двоичное число, которое выражает переходы числа связанных фигур, как указано выше.