Разбор добавил Глеб Евстропов

На первый взгляд сложная, данная задача представляет собой набор очень простых подзадач, главное правильно её на них разбить. Последовательность разбиения должна быть примерно такая: а) Ответ представляет собой некое разбиение множества кораблей на подмножества, уничтожаемые за один взрыв. Следовательно, если мы сможем для каждого подмножества проверить, возможно ли уничтожить его за один взрыв, то ответ можно будет получить перебрав все разбиения множества на подмножества (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 от центра взрыва. Взрывать бомбы можно только в целые моменты времени. Требуется уничтожить все корабли наименьшим количеством бомб.