5418번 - Giant Cover 다국어

A student at the Lutjebroek University of Technology wants to cover all buildings of the University with an enormous translucent plastic cover. This will make the use of umbrellas in this region unnecessary, significantly cutting costs.

The costs of the cover are proportional to its area. With the purpose of the cover in mind, the student wants to reduce the costs of the cover as much as possible. You are to write a program that will help him with this by calculating the minimal area of a cover.

The whole campus terrain of the University is flat and has a rectangular shape. All buildings on it have the shape of the union of a set of boxes, each of which stands on the ground. The cover must cover all buildings and will be attached to the four sides of the campus at ground level.

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:

• One line with the four integers x₁, y₁, x₂, y₂, separated by spaces, describing the campus terrain [x₁, x₂] × [y₁, y₂]. The numbers satisfy −10⁴ ≤ x₁ < x₂ ≤ 10⁴ and −10⁴ ≤ y₁ < y₂ ≤ 10⁴ .
• One line with the integer n, 0 ≤ n ≤ 400, the number of boxes that form the buildings on the campus.
• n lines, with on the i^th line the five integers a_i, b_i, c_i, d_i, h_i, separated by spaces, describing a box with footprint [a_i, c_i] × [b_i, d_i] and height h_i above the ground. The numbers satisfy x₁ ≤ a_i < c_i ≤ x₂,y₁  ≤ b_i < d_i ≤ y₂ and 0 < h_i ≤ 10⁴.

Note: [a, c] × [b, d] is a so called Cartesian product and denotes the rectangular area

For every test case in the input file, the output should contain a single number, on a single line: the area of the smallest cover, using a precision of four decimals behind the decimal point. The rounding should occur as usual; a digit is rounded up if the next digit is ≥ 5, otherwise it is rounded down.