The small sawmill in Mission, British Columbia, has
developed a brand new way of packaging boards for drying. By
fixating the boards in special moulds, the board can dry
efficiently in a drying room.
Space is an issue though. The boards cannot be too close,
because then the drying will be too slow. On the other hand,
one wants to use the drying room efficiently.
Looking at it from a 2D perspective, your task is to
calculate the fraction between the space occupied by the boards
to the total space occupied by the mould. Now, the mould is
surrounded by an aluminium frame of negligible thickness,
following the hull of the boardsâ€™ corners tightly. The space
occupied by the mould would thus be the interior of the
frame.
Input
On the first line of input there is one integer,
$N \le 50$, giving the
number of test cases (moulds) in the input. After this line,
$N$ test cases follow.
Each test case starts with a line containing one integer
$n$, $1 \le n \le 600$, which is the number
of boards in the mould. Then $n$ lines follow, each with five
floating point numbers $x, y, w,
h, v$ where $0 \le x, y,
w, h \le 10\, 000$ and $90^{\circ } < v \le 90^{\circ }$.
The $x$ and $y$ are the coordinates of the center
of the board and $w$ and
$h$ are the width and
height of the board, respectively. $v$ is the angle between the height
axis of the board to the $y$axis in degrees, positive
clockwise. That is, if $v =
0$, the projection of the board on the $x$axis would be $w$. Of course, the boards cannot
intersect.
Output
For every test case, output one line containing the fraction
of the space occupied by the boards to the total space in
percent. Your output should have one decimal digit and be
followed by a space and a percent sign (%).
Sample Input 1 
Sample Output 1 
1
4
4 7.5 6 3 0
8 11.5 6 3 0
9.5 6 6 3 90
4.5 3 4.4721 2.2361 26.565

64.3 %
