Задача 33: Прицельное метание помидор
Михаил Густокашин
В детстве у меня
было развлечение - кидаться помидорами с балкона, так чтобы
забрызгать прогнившими внутренностями помидор прохожих. Я тогда
подметил, что на каждый кубический сантиметр помидоры (кстати, она
имеет форму идеального шара) приходится квадратный метр поверхности
(это объясняется тем, что помидора падает с 7-го этажа и
размазывается по большой площади мелкими брызгами). Т.е. помидора
объемом в 3 куб. см. забрызгает круг с центром в точке падения
площадью 3 кв. м.
Я наметил несколько точек, в которые я точно попаду. В какую из этих
точек надо кинуть помидору наименьшего размера, чтобы забрызгать
всех прохожих?
Входные данные:
В первой строке входного файла input.txt содержится число n -
количество намеченных точек, в следующих n строках - координаты этих
точек с точностью до 2 знаков после запятой. В следующей строке
содержится m - количество человек, в последующих m строках -
координаты людей. 1 <= m, n <= 100. Координаты находятся в
промежутке от -100 до 100.
Выходные данные:
В первой строке содержаться координаты точки, в которую надо
кидать помидору, а во второй - наименьший радиус r помидоры в
сантиметрах.
Пример входных данных:
1
0 0
2
1 0
0.5 0.5
Пример выходных данных:
0.00 0.00
0.91
Решение:
Первая часть решения похожа на решение задачи Вирусы. Здесь
точно так же надо находить максимальное из расстояний от точки до
каждого человека, затем среди этих расстояний выбирать наименьшее.
Дальше идет интереснее. Мы нашли наилучшее R - расстояние от точки,
до самого дальнего человека. Площадь круга S = Pi * R^2. В то же
время объем шара V = 4/3 * Pi * r^3, где r - радиус помидоры в
сантиметрах. Т.к 1 куб.см. размазывается по 1 кв.м., то имеем:
R^2 = 4/3 * r^3;
r^3 = 3/4 * R^2;
Введем переменную X = 3/4 * R^2.
Все было бы хорошо, но в Паскале вроде бы нет функции которая
считает кубический корень. Его нам придется посчитать самим. Для
этого будем использовать способ двоичного приближения (дихотомии).
Минимальный возможный радиус примем равный 0, а максимальный -
заведомо больше максимально возможного (например 100, потому что
таких помидор не бывает :). Примем радиус помидоры за среднее
арифметическое минимума и максимума. Если r^3 больше X, то следует
приравнять максимум r (действительно, если объем и так больше, то
при большем радиусе он будет только увеличиваться), если r^3 меньше
X, то приравниваем минимум радиусу. Повторяем эту операцию до тех
пор, пока разница между максимумом и минимумом не станет меньше 0.01
или лучше 0.005 (так надежнее). Мы нашли кубический корень с
заданной точностью.
Кстати, примерно такой же метод используется при подсчете многих
хитрых функций в компьютере.
Далее
ð
