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

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

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

F. Ферма 2

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Стоит себе ферма. На ферме сидит фермер и считает, сколько кого есть у него. Фермер разводит верблюдов, баранов и зелёных тараканов. Когда на ферме рождается новое животное, нужно определить, кто именно родился. Тараканов от остальных фермер отличить сможет и сам, а вот для определения, верблюд это или баран, фермер созвал экспертную комиссию. Комиссия измеряет у родившегося животного два параметра — высоту горба и длину рогов. По этим данным делается заключение, к какой группе (верблюд или баран) следует отнести животное.
Эксперты действуют следующим образом: после созыва комиссии i-й эксперт выбирает 2 целых числа ai и bi, по модулю не превосходящих 2∙109. При рождении нового животного с параметрами (A, B) эксперт вычисляет выражение (aiA + biB). Если выражение положительно, то эксперт приходит к выводу, что животное — это верблюд, если отрицательное, то к выводу, что животное — это баран. Если выражение равно 0, эксперт теряется в догадках и воздерживается от каких-либо суждений.
Решение вопроса по конкретному животному комиссией производится путем голосования. Если строго больше половины экспертов голосует, что животное — верблюд, то комиссия сообщает фермеру, что на ферме стало одним верблюдом больше. В случае, если больше половины экспертов считает животное бараном, то в книгу идет запись, что родился баран. Если комиссия не может признать животное ни верблюдом, ни бараном, то фермер считает, что родился зелёный таракан.
Однажды фермер решил, что накладно оплачивать работу такого количества экспертов. Действительно, если, к примеру, комиссия состоит из 4 экспертов, при этом по всем вопросам первый соглашается с третьим, а второй — с четвёртым, то можно уволить третьего и четвёртого эксперта, не потеряв при этом в качестве работы комиссии. На ферме уже есть N верблюдов и баранов (про каждого известно, верблюд это или баран). Фермер хочет найти такое минимальное K, что комиссия из K экспертов сможет признать всех верблюдов верблюдами, а баранов - баранами (то есть каждый из экспертов сможет выбрать такую пару чисел ai и bi).

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

В первой строчке входа находится число N — общее количество верблюдов и баранов на ферме (1 ≤ N ≤ 10000). Далее расположены N строк, в каждой из которых даны 3 целых числа — параметры j-го животного: Aj — высота горба, Bj — длина рогов и Cj (1, если животное — верблюд, и 2, если баран). 0 ≤ Aj, Bj ≤ 10000.

Результат

Если не существует комиссии, удовлетворяющей требованиям фермера, выведите единственное число, равное –1. Иначе в первой строке выведите искомое число K. В следующих K строках выведите через пробел числа ai и bi — величины, которыми могут руководствоваться экперты при принятии решения. Вы можете вывести любые коэффициенты, лишь бы экспертная комиссия, вооружившись ими, приняла правильное решение по каждому из N животных.

Пример

исходные данныерезультат
2
10 0 1
0 10 2
1
1 -1
Автор задачи: Александр Ипатов
Источник задачи: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1473. Ферма 2