3266. 简单几何题

单点时限: 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:注意到有一部分橙色区域没有被覆盖。

10 人解决,41 人已尝试。

27 份提交通过,共有 374 份提交。

8.0 EMB 奖励。

创建: 7 年,4 月前.

修改: 7 年,1 月前.

最后提交: 2 年,7 月前.

来源: 2017 华东师范大学校赛

题目标签