На первый взгляд сложная, данная задача представляет собой набор очень простых подзадач, главное правильно её на них разбить.
Последовательность разбиения должна быть примерно такая:
а) Ответ представляет собой некое разбиение множества кораблей на подмножества, уничтожаемые за один взрыв. Следовательно, если мы сможем для каждого подмножества проверить, возможно ли уничтожить его за один взрыв, то ответ можно будет получить перебрав все разбиения множества на подмножества (O(n!)). Научимся для одного подмножества проверять возможно ли его уничтожение одной бомбой, а также определять, когда и в какой точке её нужно для этого сбросить.
б) Очевидно, что это невозможно сделать, если существуют два корабля, удаленные друг от друга более чем на 2 * R. Следовательно, нужно найти временной интервал, в котором таких двух кораблей в данном подмножестве нет. Пусть у нас есть два корабля, причем известно, что вектора их скоростей различны, а следовательно, с изменением времени на 1, расстояние между ними также изменяется хотя бы на 1. Интуитивно понятно, что функция расстояния между кораблями будет меняться с возрастания на убывание (или наоборот) не более одного раза. Из этого следует, что отрезок на котором два корабля будут удалены друг от друга не более чем на 2*R будет содержать в себе не более 2*R целочисленных точек (они же - моменты времени). Следовательно, пересечение этих интервалов по всем парам кораблей из подмножества также будет содержать не более 2*R целочисленных точек. Подзадачу нахождения интервала для пары кораблей (подсказка: выпишите функцию зависимости расстояния от времени) и пересечения интервалов (тривиально) решите сами. Теперь переберем все целочисленные точки в итоговом интервале, для каждой проверим, существует ли искомое место сброса бомбы.
в) Текущая подзадача: дано множество точек на плоскости, найти окружность радиуса R, содержащую внутри себя (или на границе) все данные точки или сказать что её не существует. Пусть окружность существует, тогда можно передвинуть её центр так, чтобы как минимум две точки (если их конечно больше одной, если точка одна - задача решения не требует) находились на границе. Отлично, переберем все пары точек, для каждой пары построим окружность радиуса R, с центром удалённым на R от этих двух точек (если точки не совпадают, то таких окружностей две) и для каждой из этих окружностей проверим, удовлетворяет ли она условию.
г) Таким образом, задача решениа. Перебираем все подможества, для каждого проверяем уничтожается ли оно одной бомбой, затем перебираем все разбиения исхожного множества на подножества (задача для самостоятельного решения, подсказка: рекурсивный перебор), из всех разбиений таких, что каждое подмножество уничтожеается одной бомбой, выбираем разбиение на наименьшее число подмножетсв и получаем ответ на задачу.
д) Оценим сложность алгоритма.
Оценка сверху: О(n! * n) (перебор разбиений с проверкой для каждого разбиения, оптимизирует до О(n!) проверкой в ходе перебора) + О(2^n * n^3 * (2 * R)). В худшем случае эта величина будет примерно равна 3 * 10^7 + 2^10 * 1000 * 100, что несколько многовато (130 миллионов операций, да еще на константу), но это оценка сильно сверху, так как на самом деле проверка для подмножества происходит не за О(n^3), а за О(c^3), где с - мощность подмножества, а математическое ожидание мощности подмножества равно n / 2, да и длина пересечения интервалов далеко не всегда равна 2*R (хотя можно придумать такой тест, что она почти всегда будет равна 2*R).
e) Осталось только аккуратно все эти подзадачи запрограммировать (рекомендуется щедро пользоваться функциями). Успехов в написании!
Заданы начальные координаты и скорости кораблей на плоскости. Есть бомбы, уничтожающие корабли на расстоянии не превышающем R от центра взрыва. Взрывать бомбы можно только в целые моменты времени. Требуется уничтожить все корабли наименьшим количеством бомб.
N вражеских кораблей движутся прямолинейно с постоянными скоростями. Вакуумная бомба уничтожает все объекты в радиусе R от точки взрыва (то есть все объекты, расстояние от которых до точки взрыва не больше R). Взрывать бомбу можно только в целые моменты времени.
Требуется определить, за какое наименьшее количество взрывов можно уничтожить все корабли, а также в какие моменты времени и в каких точках для этого следует произвести взрывы. Время отсчитывается от момента, когда координаты движущихся кораблей были определены со спутника.
Входные данные
В первой строке входных данных задаются целые числа N(2 <= N <= 10) и R (0 < R ≤ 50. В следующих Nстроках содержится по 4 числа, описывающих движение кораблей. Первые два числа строки – координаты корабля в момент времени 0, по модулю не превосходящие 105. Следующие два числа – значения координат вектора скорости, по модулю не превосходящие 1000. Все эти числа целые.
Гарантируется, что никакие 2 корабля не имеют одинаковые векторы скорости.Однако вполне возможно, что в какой-то момент времени два корабля пройдут через одну точку.
Выходные данные
В первой строке выведите одно число – минимальное количество взрывов K. В следующих K строках для каждого взрыва выведите по три числа: целое время взрыва и вещественные координаты взрыва, указанные с точностью не менее трех значащих цифр после точки. Разрешается производить взрывы как в разные, так и в один и тот же момент времени. Разрешается взрывы производить как в различных точках, так и в одной точке в разные моменты времени.
Если решений несколько, выведите любое из них.
Комментарий. Решения, верно работающие при N≤ 3, будут набирать не менее 50 баллов.