矩形面积

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

小度熊有一个桌面,小度熊剪了很多矩形放在桌面上,小度熊想知道能把这些矩形包围起来的面积最小的矩形的面积是多少。

Input

第一行一个正整数 T,代表测试数据组数($1 \leq T \leq 20$),接下来 T 组测试数据。

每组测试数据占若干行,第一行一个正整数 $N(1 \leq N < \leq 1000)$,代表矩形的数量。接下来 N 行,每行 8 个整数$x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4$,代表矩形的四个点坐标,坐标绝对值不会超过10000。

Output

对于每组测试数据,输出两行:

第一行输出"Case #i:",i 代表第 i 组测试数据。
第二行包含1 个数字,代表面积最小的矩形的面积,结果保留到整数位。

Sample Input

2 2 5 10 5 8 3 10 3 8 8 8 8 6 7 8 7 6 1 0 0 2 2 2 0 0 2

Sample Output

Case #1: 17 Case #2: 4

Hint

hujie

Source

2015年百度之星程序设计大赛 - 初赛(1)

提交代码