Если радиус фонтана R, то его центр должен быть на расстоянии не меньше R+Ri от i-й колонны. Соответственно если закрасить вокруг каждой колонны круги такого радиуса (и от стен закрасить полосы ширины R), то останутся только возможные места для центров фонтана

соответственно можно сделать бинарный поиск по R от нуля до условно max(H,W)/2, максимального значения, когда такие точки еще существуют

другое дело, что я не умею в задачи с числами с плавающей точкой, поэтому вот

N^3 log N прокатит же?

А просто посчитать расстояния от центра фонтана до стен холла и до каждой из колонн и выбрать минимальное - неправильно?

так этого центра нету, его найти надо

аа, я думал нету, а он есть

Ну вобщем да. Только расстояние не совсем до колонн, а с учетом радиусов колонн

Ааа, оказ центр дают 😅😅, ну да тогда задача очень простая, я думал это задача с ВКОШП 04

То есть поверить, что набор кругов полностью покрывает прямоугольник ?

ага

дан прямоугольник и набор кругов (радиусы и центры). Надо проверить, полностью ли прямоугольник покрыт кругами

А почему R + Ri ?

Радиус колонны итой, наверное (задачу не читал)

Аааа R_i

Все, ясно)

Это тот баян про колонны, рояль и корридор?

Вот есть вопрос. Пишу программу где есть двухмерная плоскость из целочисленных координат, с точкой начала, конца и всякими возможными препятствиями. Мой мозг не осилить алгоритм А*, поэтому я придумал другой. Просто двигаться по диагонали в сторону прямой на которой лежит точка конца, при этом заранее проверяем, лежит ли на прямой следующей точки стенка, если не лежит, то продолжаем двигаться по диагонали, если лежит, то просто двигаемся вперёд, пока не окажемся за стенкой, а потом опять по диагонали. Когда окажемся на одной прямой с точкой конца, просто идём напрямую к ней. Что с этим алгоритмом так или не так?

Просто так скажу: ты можешь залезть в тупик.

Просто кинуть луч и идти в ту сторону не вариант