2 人解决，3 人已尝试。
2 份提交通过，共有 8 份提交。
8.9 EMB 奖励。
2237. Box Art
单点时限: 10.0 sec
内存限制: 256 MB
The world famous artist A.A. Blox, well known for his cubic sculptures, has developed a totally new way to create impressive artwork from a rectangular solid of transparent acrylic glass. With the patented laser device of his friend T.D. Resal, he is able to change the colour of parts of the originally colourless box. Due to the prototype stadium of the laser device, he can only change the colour of a rectangular solid whose sides are parallel to the sides of the large box (“axis aligned”).
The value of the resulting object is measured by the volume of coloured acrylic glass. Since A.A. Blox is not good at mathematics, he has hired you to help him out and compute the price of his artwork for him.
For a given three-dimensional axis aligned initial box b and a set S of three-dimensional axis aligned boxes,you have to compute the volume of the union of all parts of the boxes of S that lie within b. Make sure that you count the volume of overlapping parts of the boxes only once!
输入格式
The first line contains the number of scenarios.
For each scenario you are given a line containing x1 y1 z1 x2 y2 z2, defining the two corners (x1, y1, z1), (x2, y2, z2) of the initial axis aligned box b. All numbers are separated by single blanks.
The following line contains the numberm(m <= 2000) of boxes in S whose colour was changed by the laser device, followed bymlines each containing x1 y1 z1 x2 y2 z2, defining the two corners (x1, y1, z1),(x2, y2, z2) of one of the axis aligned boxes in S. All numbers are separated by single blanks.
All coordinates are in the range from 0 to 1000, and the coordinates in each line satisfy x1 <= x2, y1 <= y2 and z1 <= z2.
输出格式
Start the output for every scenario with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a line containing the total volume of coloured acrylic glass. Terminate the output for the scenario with a blank line.
样例
Input
2 0 0 0 10 10 10 1 2 2 2 4 4 4 0 0 0 10 10 10 2 0 0 0 6 10 10 4 0 0 10 10 10
Output
Scenario #1: 8 Scenario #2: 1000
题目标签