Two opposite vertices of the parallelepiped A with the edges parallel to the datume lines, have coordinates (0, 0, 0) and (u, v, w) correspondingly (0 < u < 1000, 0 < ;v < 1000, 0 < w < 1000).
Each of the n points of the set S is defined by its coordinates (x(i), y(i), z(i)), 1 ≤ i ≤ n ≤ 50. No pair of points of the set S lies on the straight line parallel to some side of the parallelepiped A.
You are to find a parallelepiped G of the maximal volume such that all its sides are parallel to the edges of A, G completely lies in A (G and A may have common boundary points) and no point of S lies in G (but may lie on its side).
The first line consists of the numbers u, v, w separated with a space. The second line contains an integer n. The third, …, (n+2)-nd line – the numbers x(i), y(i), z(i)separated with a space.
All coordinates are non-negative, not greater than 1000 and written with not more than two digits after a decimal point.
One number – the volume of G with two digits after a decimal point. If the true volume has more than two digitrs after a decimal point you should round off the result to two digits after a decimal opint according to the common mathematical rules.
1.0 1.0 1.0
0.5 0.5 0.5
Problem Source: II Collegiate Students Urals Programming Contest. Yekaterinburg, April 3-4, 1998