Задача g6_1033: Прицельное метание помидор

Михаил Густокашин
В детстве у меня было развлечение - кидаться помидорами с балкона, так чтобы забрызгать прогнившими внутренностями помидор прохожих. Я тогда подметил, что на каждый кубический сантиметр помидоры (кстати, она имеет форму идеального шара) приходится квадратный метр поверхности (это объясняется тем, что помидора падает с 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

Решение g6_1033:
Эту задачу я составил сам. От начала до конца :).
Первая часть решения похожа на решение задачи #1010 - Вирусы. Здесь точно так же надо находить максимальное из расстояний от точки до каждого человека, затем среди этих расстояний выбирать наименьшее.
Дальше идет интереснее. Мы нашли наилучшее 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 (так надежнее). Мы нашли кубический корень с заданной точностью.
Кстати, примерно такой же метод используется при подсчете многих хитрых функций в компьютере.