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

Уральская региональная командная олимпиада по программированию 2011

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

K. День рождения энта

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Problem illustration
У энта Феди скоро день рождения. Его друзья решили испечь ему праздничный торт. Проблема в том, что энты живут так долго, что никто уже и не помнит, кому сколько лет. Так что Феде сделали торт просто c большим количеством свечек. Узнав об этом, энт Саша, помнивший всё на свете, возмутился и заявил, что Феде исполняется ровно k лет. Благо на торте было n свечек (n > k). Раз стал известен точный возраст Феди, было решено вырезать из торта выпуклый многоугольный кусок ненулевой площади, содержащий ровно k свечек (считаются свечки, расположенные внутри и на границе куска).
Торт для Феди представляет из себя квадрат размером 2 · 109 на 2 · 109 миллиметров. Каждая свечка удалена на целое положительное число миллиметров от каждой из сторон торта.

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

В первой строке записаны целые числа n и k (1 ≤ k < n ≤ 1 000). Далее в n строках следуют пары целых чисел — координаты свечек. Начало координат расположено в центре торта, а координатные оси параллельны его сторонам. Все координаты строго меньше 109 по модулю. Гарантируется, что нет двух свечек в одной точке.

Результат

В первой строке выведите целое число m — количество вершин многоугольника, который нужно вырезать из торта (3 ≤ m ≤ 10 000). Далее в m строках перечислите координаты вершин этого многоугольника в порядке обхода против часовой стрелки. Координаты должны быть целыми числами, по модулю не превышающими 109. Углы при вершинах многоугольника не должны быть развёрнутыми. Длины всех сторон должны быть ненулевыми. Если существует несколько решений, можно вывести любое из них. Гарантируется, что существует хотя бы одно решение, удовлетворяющее описанным ограничениям.

Пример

исходные данныерезультат
5 3
1 0
1 2
2 1
3 0
3 2
3
1 0
2 1
1 2
Автор задачи: Денис Мухаметьянов
Источник задачи: Уральская региональная командная олимпиада по программированию 2011
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1883. День рождения энта