Giant Cover

A student at the Lutjebroek University of Technology wants to cover every building on campus with one enormous translucent plastic sheet. Nobody in the area would need an umbrella after that, which cuts costs a lot.

The price of the sheet is proportional to its area, so the student wants the smallest cover possible. Write a program that computes that minimum area.

The campus terrain is flat and rectangular. Every building is a union of boxes standing on the ground, and boxes may overlap. The cover has to lie above all buildings and is fastened to the four sides of the campus at ground level.

The sheet is pulled tight, so the solid enclosed by the cover and the ground is convex. Report the area of the smallest cover that meets these conditions. The ground rectangle itself does not count toward that area.

The first line contains the number of test cases. Each test case has the following format.

• One line with four integers $x_1$, $y_1$, $x_2$, $y_2$ separated by spaces. The campus terrain is $[x_1, x_2] \times [y_1, y_2]$, with $-10^4 \le x_1 < x_2 \le 10^4$ and $-10^4 \le y_1 < y_2 \le 10^4$.
• One line with the integer $n$, the number of boxes that form the buildings, where $0 \le n \le 400$.
• $n$ lines. The $i$th of them holds five integers $a_i$, $b_i$, $c_i$, $d_i$, $h_i$ separated by spaces, describing a box with footprint $[a_i, c_i] \times [b_i, d_i]$ and height $h_i$ above the ground. They satisfy $x_1 \le a_i < c_i \le x_2$, $y_1 \le b_i < d_i \le y_2$ and $0 < h_i \le 10^4$.

Here $[a, c] \times [b, d]$ is a Cartesian product, the rectangular area of all points $(x, y)$ with $a \le x \le c$ and $b \le y \le d$.

For every test case, print the area of the smallest cover on one line, with four digits after the decimal point. Round the usual way: a digit is rounded up when the next digit is 5 or more, and rounded down otherwise.