Да будет свет
Вы хотите, чтобы общая интенсивность освещения в целевой точке была максимальной. Для этого можно удалить некоторые воздушные шары, которые блокируют свет. Однако из-за затрат на удаление существует ограничение на количество шаров, которые можно убрать. Таким образом, вам нужно выбрать такой набор шаров для удаления, чтобы максимизировать интенсивность освещения в целевой точке.
Следующая иллюстрация показывает конфигурацию, описанную в первом наборе данных из примера ввода ниже. На рисунке изображена xy-плоскость, что достаточно, так как в этом наборе данных z-координаты всех источников света, центров шаров и целевой точки равны нулю. На рисунке источники света обозначены звездочками, а шары — кругами. Целевая точка находится в начале координат, и можно удалить до 4 шаров. В этом случае пунктирные круги на рисунке обозначают шары, которые следует удалить.
Рисунок 1: Первый набор данных из примера ввода.
Входные данные
Ввод состоит из последовательности наборов данных. Каждый набор данных имеет следующий формат.
N M R
S_1x S_1y S_1z S_1r
...
S_Nx S_Ny S_Nz S_Nr
T_1x T_1y T_1z T_1b
...
T_Mx T_My T_Mz T_Mb
E_x E_y E_z
Первая строка набора данных содержит три положительных целых числа: N, M и R, разделенные пробелом. N — количество шаров, не превышающее 2000. M — количество источников света, не превышающее 15. R — количество шаров, которые можно удалить, не превышающее N.
Каждая из следующих N строк содержит четыре целых числа, разделенных пробелом. (S_ix, S_iy, S_iz) — координаты центра i-го шара, а S_ir — его радиус.
Каждая из следующих M строк содержит четыре целых числа, разделенных пробелом. (T_jx, T_jy, T_jz) — координаты j-го источника света, а T_jb — его яркость.
Последняя строка набора данных содержит три целых числа, разделенных пробелом. (E_x, E_y, E_z) — координаты целевой точки.
S_ix, S_iy, S_iz, T_jx, T_jy, T_jz, E_x, E_y и E_z больше -500 и меньше 500. S_ir больше 0 и меньше 500. T_jb больше 0 и меньше 80000.
В целевой точке интенсивность света от j-го источника обратно пропорциональна квадрату расстояния, а именно
если никакой шар не прерывает свет. Общая интенсивность освещения — это сумма вышеуказанного.
Вы можете предположить следующее.
Расстояние между целевой точкой и любым источником света не менее 1.
Для каждого i и j, даже если S_ir изменяется на ϵ (|ϵ| < 0.01), не изменяется, скрывает ли i-й шар j-й свет или нет.
Конец ввода обозначается строкой из трех нулей.
Выходные данные
Для каждого набора данных выведите строку с десятичной дробью, представляющей наивысшую возможную интенсивность освещения в целевой точке после удаления R шаров. Ошибка в выводе не должна превышать 0.0001.