Лягушки, задача про лягушек :) Опции

[Скрытная]

Лягушки
Время на тест: 3 секунды
Как-то раз собрались лягушки в путешествие, как говорится, мир повидать и себя показать. Долго они шли и наткнулись на реку, через которую надо было переправится. Река представляет собой две параллельные прямые. В этой речке (между этими двумя прямыми) есть N кочек, по которым лягушки могут прыгать, но дело в том, что после того как лягушка прыгнула на кочку, она сразу тонет, т.е. прыгать по ней больше нельзя. Кочки представляют собой точки с координатами (Xi, Yi). Но дело в том, что каждая лягушка может прыгать не более чем на расстояние R. Первоначально лягушки располагаются на первом берегу (на первой прямой) и могут начинать прыгать с любой точки прямой, аналогично и заканчивать они могут в любом месте второго берега (в любой точке второй прямой) . Вам необходимо переправить максимальное количество лягушек. Гарантируется что расстояние между прямыми больше числа R.

Ограничения и уточнения:
0 < N < 300
-1000 < A1, A2, B1, B2, C1,C2 < 1000
0 < R < 1000
Гарантируется, что все точки находятся между этими двумя прямыми.
Все вещественные числа вводятся с точность до двух знаков после точки.
Никакие две точки не имеют одинаковые координаты.

Входные данные: InPut.txt
В первой строке три вещественных числа A1,B1,C1 – коэффициенты первой прямой
Во второй строке три числа - A2, B2, C2 – коэффициенты второй прямой
В третьей 2 числа – целое N и вещественное R
Далее идут N строчек - координаты кочек(точек) Xi Yi

Выходные данные: OutPut.txt
В первой строке одно число M – количество переправленных лягушек.
Далее идет M строк – описание пути каждой лягушки:
Первое число Ki – количество использованных кочек, далее Ki чисел – номера этих кочек в том порядке, в котором лягушка по ним прыгала.

InPut.txt OutPut.txt
0 1 0 3
0 1 –5 2 2 4
6 2.25 2 1 3
1 2 2 6 5
3 2
3 3
3 4
4 4
5 2

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

Сообщение отредактировано: Скрытная - 22.12.2007 1:07

[Скрытная]

2 Michael_Rybak ну, да... задача олимпиадная... а это имеет какое-то значение?