题目描述

$2022$ 年是冬奥会之年！冰壶一直是最受欢迎的冬季运动之一，因为它需要技巧、策略，有时还需要一点运气。

在一场冰壶比赛中，$2$ 支队伍通过在长冰道上滑动沉重的花岗岩石块进行比赛。我们称这两支队伍为 红队 和 黄队，因为他们的石头通常用红色和黄色手柄区分。一场冰壶比赛由若干 局（子比赛）组成；在每一局中，每队各拥有 $8$ 块石头，轮流将其滑过长冰道，朝向一个称为 大本营 的圆形目标区域。石头可能会击中已有的石头，从而改变自身的运动方向以及其他石头的位置（包括将其撞出比赛）。大致来说，一队的目标是让自己的石头尽可能靠近大本营的中心。

在几何上，大本营和石头可以分别建模为一个圆和一个圆盘（圆所围成的区域），每局结束时的计分规则正式总结如下。

• 每块石头可视为二维平面上的一个半径为 $R_s$ 的圆盘。
• 大本营是以 $(0,0)$ 为圆心、半径为 $R_h$ 的圆。
• 计分时只考虑 在大本营内 的石头。如果一块石头的任何部分位于代表大本营的圆上或圆内，则认为该石头在大本营内。相切也算在内。
• 对于一队在营内的每块石头，如果没有对方队伍的石头比它更靠近圆心（按欧几里得距离），则该队获得 $1$ 分。本题中假设没有两块石头与圆心 $(0,0)$ 的距离相等。

两支队伍正在比赛，并且已经投出了他们所有的石头。红队还剩下 $N$ 块石头在冰道上，圆心分别为 $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$；黄队还剩下 $M$ 块石头，圆心分别为 $(Z_1, W_1), (Z_2, W_2), \dots, (Z_M, W_M)$。现在要求你计算出两队各自的得分。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个空格分隔的整数 $R_s$ 和 $R_h$。

下一行包含整数 $N$。然后 $N$ 行，其中第 $i$ 行包含两个空格分隔的整数 $X_i$ 和 $Y_i$。

之后，类似地，下一行包含整数 $M$。在接下来的 $M$ 行中，第 $i$ 行包含两个空格分隔的整数 $Z_i$ 和 $W_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y z，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是红队的得分，$z$ 是黄队的得分。

2
1 5
4
1 -1
6 1
0 6
-5 0
0
10 100
2
-3 -4
200 200
0

Case #1: 3 0
Case #2: 1 0

2
1 5
2
1 0
-3 0
1
0 2
10 50
2
-40 -31
-35 70
3
59 0
-10 0
30 40

Case #1: 1 0
Case #2: 0 2

提示

在本例中，黄队在大本营内没有石头，因此红队在大本营内的每块石头获得 $1$ 分。除圆心在 $(6, 1)$ 的石头外，所有石头都在大本营内（如果圆心在 $(6, 0)$ 处，它将会触及大本营边界），所以红队得到 $3$ 分。

在附加样例中，两队都有石头在大本营内。红队位于 $(1, 0)$ 的石头在大本营内，并且没有黄队的石头比它更靠近大本营中心，因此它值得 $1$ 分。

尽管另一块红队石头（圆心在 $(-3, 0)$）也在大本营内，但它不值得得分，因为圆心在 $(0, 2)$ 的黄队石头比它更靠近圆心 $(0, 0)$。这块黄队石头也不值得得分，因为存在红队位于 $(1, 0)$ 的石头。因此，红队获得 $1$ 分，黄队获得 $0$ 分。

限制条件

$1 \le T \le 100$。

$1 \le R_s < R_h \le 10^4$。

$0 \le N \le 8$。

对于所有 $i$，$-2 \times 10^4 \le X_i \le 2 \times 10^4$。

对于所有 $i$，$-2 \times 10^4 \le Y_i \le 2 \times 10^4$。

对于所有 $i$，$-2 \times 10^4 \le Z_i \le 2 \times 10^4$。

对于所有 $i$，$-2 \times 10^4 \le W_i \le 2 \times 10^4$。

每块石头的圆心到圆心 $(0,0)$ 的距离均不相同，即没有两块石头与圆心等距。

没有两块石头重叠（但两块石头可以相切）。

测试集 1

$M = 0$。

测试集 2

$0 \le M \le 8$。

翻译由 DeepSeek V4 Pro 完成