题目描述

有 $n$ 个矩形木条，你需要用一个面积尽可能小的凸多边形把它们围起来，并计算出木条占整个包装面积的百分比，如下图所示：

本题有多组数据。

输入格式

第一行一个正整数 $T$，表示数据组数。

接下来为 $T$ 组数据，每组数据的第一行为木条个数 $n$ 。以下 $n$ 行每行五个整数 $x,y,w,h,j$，其中 $(x,y)$ 是木条中心的坐标，$w$ 是宽，$h$ 是高，$j$ 是长度为 $w$ 的边相对 X 轴顺时针旋转的角度(例如 $j=0$ 时长度为 $w$ 的边应是水平方向)。木条保证不相交。

输出格式

输出共 $T$ 行，每行一个浮点数和符号 "%",表示木条占整个包装面积的百分比，保留一位小数即可。

输入输出样例

输入#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

输出#1

64.3 %

数据规模与约定

对于 $100\%$ 的数据，$1\leq T \leq 50,2 \leq n \leq 600,0\leq x,y,w,h \leq 10^4,-90 \leq j \leq 90$。