22748_TheGoldenCeiling

The main office of the Bank of Zork was built in the Aragain Village (later know as Flatheadia) in the year 722 of the Great Underground Empire (GUE). In 788 GUE, the chairman, J. Pierpont Flathead, decided (shortly before unexplained disappearance in 789), that it was time to completely redesign the already ornate bank atrium with a ceiling covered in brilliant gold leaf.

This new ceiling was not your ordinary ceiling. Although the atrium is essentially a big box, the ceiling would be slanted (supposedly, making the atrium look bigger). At the time, the exact dimensions of the rectangular atrium and the slope and location of the slanted ceiling gad not been finalized. Flathead wanted to know how much gold leaf he would have to order from the Frobozz Magic Gold Leaf Company to cover the ceiling for different atrium dimensions and ceiling slants. He also wanted to allow the slanted part to possibly hit the floor of the box and/or the top of the box.

Consider the following rough sketches of some possible atrium configuration:

Note: The dashed outline represents the original box, the horizontally ruled surface is the slanted part of the ceiling and the cross hatched surface is the part of the top of the box not cut off by the plane. The walls and floor of the atrium are transparent. The total area to be covered (the ceiling ) is the slanted part plus any part of the top of the original box that is not cut off by the plane.

Your job is to write a program that Flathead could have used to calculate the amount gold leaf required to cover the ceiling for a particular configuration.

As a sad epilogue, the main branch was brought to ruins when the Curse of Megaboz befell it in 883GUE. Between the barbarian invasions of the 880's and the countless looters that had tread the underground ruins in the years that followed, the entire bank with all its valuables, as well as its very expensive gold leaf ceiling, had been removed or vandalized. More information can be found on-line at: http://www.thezorklibrary.com/hostory/bank_of_zork.html.

The first line of input contains a single integer P, ( 1 ≤ P ≤ 1000 ), which is the number of data sets that follow. Each data set is a single line that contains the data set number, N, followed by a space, followed by seven space separated double precision floating point values, L, W, H, A, B, C and D. The values L, W and H specify the length, width and height of the atrium in Flathead Units (FU's), respectively, and are always positive values. The values A, B, C and D specify the coefficients of the plane equation for the slanted part of the ceiling:

Ax + By + Cz = D

where: 0 ≤ x ≤ L, 0 ≤ y ≤ W, 0 ≤ z ≤ H .

One corner of the original box is always at the origin (0, 0, 0 ) and the other at (L, W, H). The plane will never be vertical (C will be ≥ 1.0) and the plane will always pass through the interior of the box (there will be points (x, y, z) in the box and strictly above the plane (Ax + By + Cz > D). and others strictly below the plane (Ax + By + Cz < D).

For each data set there is one line of output. It contains the data set number (N) followed by a single space, followed by an integer value that is the number of square FU's required to cover the ceiling in gold leaf (rounded up to the next square FU).

3
1 10 12 15 -1.3 1 1.1 3.5
2 10 12 10 -1.3 1 1.1 11
3 13 9 10 -1.3 1 1.1 0

1 166
2 164
3 144