Наибольший параллелепипед
Первоисточник: Неофициальный сайт белорусских олимпиад. Задачи со сборов к IOI (2002-2003). Параллелепипед
URL первоисточника: http://byoi.narod.ru/
Задачу добавил: elena
Успешно сдано решений: 0
Время на тест - 2 с.
Прямоугольный параллелепипед А с ребрами, параллельными осям координат, задан своими двумя противоположными вершинами с координатами (0,0,0) и (u,v,w) соответственно. Также задано множество S, содержащее n точек, тройками их координат (x(i), y(i), z(i)), 1 <= i <= n <= 50, при этом ни одна пара точек из S не лежит на прямой, параллельной какой-либо грани параллелепипеда A.
Нужно найти прямоугольный параллелепипед G максимального объема, такой, что
- все его ребра параллельны ребрам A,
- G полностью лежит в A (G и A могут иметь общие граничные точки),
- ни одна точка из S не лежит внутри G (но может лежать на его границе).
Формат входного файла input.txt:
Первая строка содержит вещественные числа u, v, w через пробел
Вторая строка содержит целое число n
В каждой из следующих n строк содержатся вещественные координаты очередной точки множества x(i), y(i), z(i) через пробел
Вещественные числа записаны не более чем с двумя десятичными знаками после запятой. Все числа во входном файле неотрицательны и не превосходят 1000.
Формат выходного файла output.txt:
Первая строка - единственное число - величина объема параллелепипеда G с двумя десятичными знаками после запятой.
Пример входного файла
1.0 1.0 1.0
1
0.5 0.5 0.5
Пример выходного файла
0.50