eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Супутники-шпигуни

Супутники-шпигуни

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Марсіанські супутники-шпигуни сфотографували ділянку території на темній стороні Місяця. У темноті виявилось видно лише множину точок, що світяться. Самий головний марсіанин припустив, что точки — це секретні об'єкти лунатиків на їхніх військових базах. Перед тим, як готуватись до вторгнення на Місяць, непогано було б взнати, скільки усього військових баз є у лунатиків. Оскільки, крім отриманої фотографії, іншої інформації у розвідки немає, експерти взялись порахувати кількість баз, які видно на фотографії. Марсіани вважають, що базам на фотографії відповідають скупчення точок, що світяться, які задовольняють наступній властивості: відстань між довільнии двома об'єктами на одній базі строго менше, ніж відстань від довільного об'єкта на цій базі до довільного об'єкта на іншій військовій базі. Ділянку на фотографії наближено можна вважати плоскою, відстань між об'єктами, які на фотографії мають координати (A, B) та (С, D), вважати рівною

.

Вхідні дані

Вхідні дані складаються з декількох блоків тестових даних. У першому рядку блоку знаходиться ціле додатне число N — кількість об'єктів на фотографії. У наступних N рядках задано координати об'єктів (у кожному рядку дві координати чергового об'єкту, відокремлені пропуском). Координати — цілі числа, які по модулю не перевищують 10^4. Останній блок складається з єдиного числа 0. Блоки відокремлюються один від одного порожнім рядком. Сума N не перевищує 5000, сума N^2 не перевищує 400000, сума N^3 не перевищує 250000000.

Вихідні дані

Програма повинна визначити за отриманою інформацією можливі кількості баз, які видно на фотографії. Для кожного тесту необхідно вивести рядок з 0 та 1 довжини N. Так рядок 110 означає, що на фотографії може бути видно 1 або 2 бази, рядок 0112 або 3 бази.

Автор Дмитро Іванков
Джерело Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006