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

MSU SE and Ural SU contest. Petrozavodsk training camp. Summer 2005

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

I. Фотография

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Река течёт по равнине вдоль прямой y = 0. На равнине по обеим сторонам реки (но не на самой реке) растут деревья. В точке (0,0) на реке находится плотина. Необходимо сделать с плотины две одинаковых фотографии разных сторон реки. Фотографии считаются одинаковыми, если расположение деревьев на них — одинаковое (учитывается только расположение по горизонтали, а расстояние до деревьев не учитывается).
Если некоторое дерево загорожено другим, то на фотографии его не видно. Никакие два дерева не находятся в одной точке. Размером фотоаппарата и деревьев можно пренебречь.
Фотографирование происходит следующим способом: сначала используется фотоаппарат с углом раствора, сколь угодно близким к 180 градусам (фотоплёнка представляет собой прямую, деревья, расположенные перед плёнкой, центрально проектируются на неё с центром (0,0)), затем из фотографии вырезается некоторый отрезок, содержащий деревья только с одной стороны реки, и масштабируется произвольным образом.

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

На каждой строчке, кроме последней, находятся два целых числа, не превосходящих 20000 по модулю — координаты деревьев. Количество деревьев не более 105.
На последней строчке стоит два нуля.

Результат

Вывести максимальное количество деревьев на двух одинаковых фотографиях разных сторон реки.

Примеры

исходные данныерезультат
-1 1
0 1
2 1
3 1
7 2
3 -2
1 -1
0 -1
0 -5
-4 -2
-3 -1
0 0
4
0 1
1 1
2 1
-3 -1
-2 -2
-1 -3
0 0
3
Автор задачи: Андрей Румянцев
Источник задачи: Petrozavodsk summer training camp, August 2005.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1388. Фотография