Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Автоспорт

(Время: 2 сек. Память: 32 Мб Сложность: 64%)

В кружке автомоделирования проводятся соревнования. Они проходят на прямом участке трассы длиной L и шириной W. N участников выставляют свои модели на стартовые позиции. По свистку все модели начинают движение.

Цель состязания – быстрее всех доехать до линии финиша. Однако в пути каждую модель подстерегают опасности. А именно, модель может врезаться в борта трассы и тем самым прекращать движение, или две и более модели могут столкнуться и также остановиться.

Введем систему координат, в которой ось OX будет направлена вдоль протяжения трассы, а ось OY – поперек ему. Тогда трасса является прямоугольником, ограниченным прямыми y = 0, y = W, x = 0 и x = L.

Модель считается врезавшейся в борт трассы, если в некоторый момент времени ее y-координата будет равна либо 0, либо W. Две модели считаются столкнувшимися, если в некоторый момент времени их координаты совпадают. Модели можно считать материальными точками.

Модель побеждает в соревновании, если она успешно преодолела линию финиша (прямую x = L) и сделала это не позже любой другой модели. Возможно, что побеждает сразу несколько моделей, в этом случае, как говорится, «побеждает дружба». Возможно также, что ни одна модель по тем или иным причинам не сумеет преодолеть линию финиша.

Заметим отдельно, что если модель проходит через какую-либо из точек (L, 0) или (L, W), то считается, что она врезается в борт.

Поведение большинства моделей довольно предсказуемо, поэтому часто можно предугадать ход состязания. В данной задаче мы будем приближенно считать, что все модели начинают двигаться из своих начальных точек с заданными, постоянными на протяжении соревнования, векторами скорости.

Входные данные

В первой строке входного файла INPUT.TXT находятся три числа N, L, W. (1 ≤ N ≤ 1000, 1 ≤ L ≤ 104, 2 ≤ W ≤ 104).

В последующих N строках находятся описания соревнующихся моделей по 4 целых числа xi, yi, vxi, vyi, 1 ≤ i ≤ N . (xi, yi) – это координаты стартовой точки модели с номером i, (vxi, vyi) – вектор скорости этой модели.

Гарантируется, что стартовые точки всех моделей различны, находятся на трассе, и не располагаются ни на каком-либо борту трассы, ни на линии финиша. Координаты векторов скорости не превышают 104 по абсолютному значению.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите количество победителей. Во второй строке выведите их номера в порядке возрастания.

Примеры

INPUT.TXTOUTPUT.TXT
11 1 2
0 1 1 0
1
1
22 10 3
0 1 2 0
5 2 1 0
2
1 2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 Четвертая личная олимпиада
 Пятая личная олимпиада
 A. Дробь-2
 B. Автоматизированное управление доставкой
 C. Перестановка
 D. Автоспорт

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru