УЧЕБНО - ТРЕНИРОВОЧНЫЕ СБОРЫ К IOI 2003 ДЕНЬ №9 Параллелепипед
Входной файл: input.txt Выходной файл: output.txt Время на тест: 2 секунды Тесты к задаче:Скачать
Две противоположные вершины прямоугольного параллелепипеда A с ребрами, параллельными осям координат, имеют координаты (0,0,0) и (u,v,w) соответственно (0Множество S из n точек задается тройками координат (x(i), y(i), z(i)), 1 <= i <= n <= 50, при этом ни одна пара точек из S не лежит на прямой, параллельной какой-либо грани A.
Найти такой прямоугольный параллелепипед G максимального объема, что все его ребра параллельны ребрам A, G полностью лежит в A (G и A могут иметь общие граничные точки) и ни одна точка из S не лежит внутри G (но может лежать на его границе).
Входной файл INPUT.TXT имеет следующий формат:
в 1-ой строке : числа u, v, w, разделенные одним пробелом
во 2-ой строке : число n
в 3-ей, ... (n+2)-ой строках : числа x(i), y(i), z(i) разделенные одним пробелом
Число n записано без десятичной точки, остальные числа записаны не более чем с двумя десятичными знаками после десятичной точки (если число целое, точка может быть опущена). Все числа во входном файле неотрицательны и не превосходят одной тысячи.
Программа должна выдавать в выходной файл OUTPUT.TXT единственное число - величину объема G с двумя десятичными знаками. В случае, если истинный объем параллелепипеда G содержит больше двух десятичных знаков, следует произвести округление до двух знаков по обычным математическим правилам.