printРабочее место участника

printЗадачи

840. Морской бой

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

`N` вражеских кораблей движутся прямолинейно с постоянными скоростями. Вакуумная бомба уничтожает все объекты в радиусе R от точки взрыва (то есть все объекты, расстояние от которых до точки взрыва не больше `R`). Взрывать бомбу можно только в целые моменты времени.
Требуется определить, за какое наименьшее количество взрывов можно уничтожить все корабли, а также в какие моменты времени и в каких точках для этого следует произвести взрывы. Время отсчитывается от момента, когда координаты движущихся кораблей были определены со спутника.
В первой строке входного файла записаны целые числа `N` (`2\ ≤\ N\ ≤\ 10`) и `R` (`0\ <\ R\ ≤\ 50`).
В следующих `N` строках записаны по 4 числа, описывающие движение кораблей. Первые два числа строки – координаты корабля в момент времени 0, по модулю не превосходящие `10^5`. Следующие два числа – значения координат вектора скорости, по модулю не превосходящие 1000. Все эти числа целые.
Гарантируется, что никакие 2 корабля не имеют одинаковые векторы скорости. Однако вполне возможно, что в какой-то момент времени два корабля пройдут через одну точку.
В первой строке выведите одно число – минимальное количество взрывов `K`.
В следующих `K` строках для каждого взрыва выведите по три числа: целое время взрыва и вещественные координаты взрыва, указанные с точностью не менее трех значащих цифр после точки. Разрешается производить взрывы как в разные, так и в один и тот же момент времени. Разрешается взрывы производить как в различных точках, так и в одной точке в разные моменты времени.
Если решений несколько, выведите любое из них.

Пример ввода 1

3 3
-3 3 1 0
0 -6 0 2
-8 6 4 -1

Пример вывода 1

1
3 2.000 1.500

Пример ввода 2

2 1
-4 -4 2 2
2 2 -2 -2

Пример вывода 2

2
0 -4.000 -4.000
0 2.000 2.000
Решения, верно работающие при `N\ ≤\ 3`, будут набирать не менее 50 баллов.
Московская городская олимпиада школьников по информатике, 2008
loading