「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现)

B. 简单几何题

单点时限: 5.0 sec

内存限制: 256 MB

问多个圆能否覆盖一个长方形是困难的,这可能需要很多时间来解决。但是聪明的你不仅能够解决上述的问题,你甚至还能解决两个圆能否覆盖一个长方形的问题。

现在给出一个 xOy 平面上的、与坐标轴平行的长方形,长方形左下角的坐标是 $(0,0)$,右上角的坐标是 $(a,b)$;和两个圆,圆心坐标分别为 $(x_1, y_1), (x_2, y_2)$,半径分别为 $r_1, r_2$,问对于是否对一切的 $0 \leq x \leq a, 0 \leq y \leq b$ 满足 $\sqrt{(x - x_1)^2 + (y - y_1)^2} \leq r_1 \lor \sqrt{(x - x_2)^2 + (y - y_2)^2} \leq r_2$,即这两个圆能否覆盖长方形?

输入格式

输入第一行给出数据组数 $T$ $(1 \leq T \leq 10^5)$。

接下来 $T$ 行,每行一组测试数据,8 个用空格隔开的整数 $a, b, x_1, y_1, x_2, y_2, r_1, r_2$ $(1 \leq a, b, r_1, r_2 \leq 10^5, -10^5 \leq x_1, x_2, y_1, y_2 \leq 10^5)$。

输出格式

对于每组测试数据,输出一行 Case x: y。x 表示测试数据编号(从 1 开始),如果能覆盖,y 为 YES,否则为 NO

样例

Input
2
1 1 0 0 1 1 1 1
4 1 2 0 3 1 2 1
Output
Case 1: YES
Case 2: NO

提示

样例 1:蓝色和绿色区域(圆,包含边界)恰好覆盖橙色区域(长方形,包含边界)。

样例 2:注意到有一部分橙色区域没有被覆盖。