Автоспорт

В кружке автомоделирования проводятся соревнования. Они проходят на прямом участке трассы длиной 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 ≤ 10⁴, 2 ≤ W ≤ 10⁴).

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

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

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

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

Примеры

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

[Обсуждение] [Все попытки] [Лучшие попытки]