Успадкувати сфери#3202

Успадкувати сфери

1 секунда

64 мегабайти

Дуже складна

У році $2 xxx$ команда експедиції, яка висадилася на планеті, виявила дивні об'єкти, створені давньою цивілізацією, що мешкала на цій планеті. Це прозорі коробки, які містять непрозорі тверді сфери (Рисунок 1). Також були знайдені численні літографії, де, здається, вказані координати центрів і радіуси цих сфер.

Рисунок 1. Дивний об'єкт

Спочатку їхнє призначення було невідоме, але професор Замбендорф з'ясував, що важливу роль відіграє перетин, створений горизонтальною площиною. Наприклад, перетин об'єкта змінюється, як показано на Рисунку 2, коли площина рухається знизу вгору.

Рисунок 2. Перетини на різних рівнях

Він врешті-решт з'ясував, що певна інформація закодована змінами кількості зв'язних фігур у перетині. Кожна зв'язна фігура — це об'єднання кіл, що перетинаються або дотикаються одна з одною, і кожне коло — це перетин відповідної сфери. Наприклад, у Рисунку 2, геометрія якого описана у першому прикладі нижче, кількість зв'язних фігур змінюється так: $0$ , $1$ , $2$ , $1$ , $2$ , $3$ , $2$ , $1$ , $0$ при $z = 0.0000$ z = 0.0000, $162.0000$ , $167.0000$ , $173.0004$ , $185.0000$ , $191.9996$ , $198.0000$ , $203.0000$ , $205.0000$ відповідно. Якщо позначити збільшення одиницею, а зменшення — нулем, ці переходи можна записати як $8$ -бітове двійкове число $11011000$ .

Для подальшого аналізу напишіть програму, яка визначає ці переходи під час переміщення горизонтальної площини знизу $z = 0$ z = 0 вгору $z = 36000$ z = 36000.

Вхідні дані

Вхід складається з кількох наборів даних. Кожен набір починається з рядка, що містить додатне ціле число $N$ — кількість сфер у наборі. Далі йдуть $N$ рядків, кожен з яких містить чотири додатні цілі числа $X_{i}$ X_i, $Y_{i}$ Y_i, $Z_{i}$ Z_i і $R_{i}$ R_i ( $i = 1, \dots, N$ i = 1, \ldots, N), які задають координати центра і радіус $i$ -ї сфери.

Гарантується, що $1 \leq N \leq 100$ 1 \leq N \leq 100, $1 \leq R_{i} \leq 2000$ 1 \leq R_i \leq 2000, $0 < X_{i} - R_{i} < X_{i} + R_{i} < 4000$ 0 < X_i - R_i < X_i + R_i < 4000, $0 < Y_{i} - R_{i} < Y_{i} + R_{i} < 16000$ 0 < Y_i - R_i < Y_i + R_i < 16000, $0 < Z_{i} - R_{i} < Z_{i} + R_{i} < 36000$ 0 < Z_i - R_i < Z_i + R_i < 36000. Кожна сфера визначається як сукупність всіх точок $(x, y, z)$ (x, y, z), які задовольняють $(x - X_{i})^{2} + (y - Y_{i})^{2} + (z - Z_{i})^{2} \leq R_{i}^{2}$ (x - X_i)^2 + (y - Y_i)^2 + (z - Z_i)^2 \leq R_i^2.

Одна сфера може містити інші сфери. Жодна пара сфер не є взаємно дотичними. Будь-які $Z_{i} \pm R_{i}$ Z_i \pm R_i і мінімальна/максимальна $z$ -координата кола, що утворюється при перетині двох сфер, різняться принаймні на $0.01$ .

Кінець вхідних даних позначається рядком, що містить нуль.

Вихідні дані

Для кожного набору даних ваша програма повинна вивести два рядки. У першому має бути ціле число $M$ — кількість переходів. У другому — $M$ -бітове двійкове число, яке виражає ці переходи у зміні числа зв'язних фігур, як описано вище.

Приклади

Приклад 1