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

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

K. Спутники-шпионы

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Марсианские спутники-шпионы сфотографировали участок территории на тёмной стороне Луны. В темноте оказалось видно только множество светящихся точек. Самый главный марсианин предположил, что точки — это секретные объекты лунатиков на их военных базах. Прежде, чем готовиться к вторжению на Луну, неплохо было бы узнать, сколько всего военных баз имеется у лунатиков. Поскольку, кроме полученной фотографии, другой информации у разведки нет, эксперты взялись подсчитать количество баз, видных на фотографии. Марсиане считают, что базам на фотографии отвечают скопления светящихся точек, удовлетворяющие следующему свойству: расстояние между любыми двумя объектами на одной базе строго меньше, чем расстояние от любого объекта на этой базе до любого объекта на другой военной базе. Участок на фотографии приближённо можно считать плоским, расстояние между объектами, на фотографии имеющими координаты (A, B) и (С, D), полагается равным sqrt((AC)2 + (BD)2).

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

Входные данные состоят из нескольких блоков тестовых данных. В первой строке блока находится целое положительное число N — количество объектов на фотографии. В следующих N строках даны координаты объектов (в каждой строке две координаты очередного объекта, разделённые пробелом). Координаты — целые числа, по модулю не превосходящие 104. Последний блок состоит из единственного числа 0. Блоки отделяются друг от друга пустой строкой. Сумма N не превосходит 5 000, сумма N2 не превосходит 400 000, сумма N3 не превосходит 250 000 000.

Результат

Программа должна определить по полученной информации возможные количества баз, видных на фотографии. Для каждого теста необходимо вывести строку из 0 и 1 длины N. Так строка 110 означает, что на фотографии может быть видно 1 или 2 базы, строка 011 — 2 или 3 базы.

Пример

исходные данныерезультат
4
-1 -1
1 1
1 -1
-1 1

4
1 0
2 4
1 1
0 1

0
1001
1101
Автор задачи: Дмитрий Иванков
Источник задачи: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1478. Спутники-шпионы