← 返回题目列表

Codeforces · 2074/D

D. 计数点

中文机器翻译题面 查看原题

粉红士兵以他们的中心画了 $$$n$$$ 圆圈 $$$x$$$ 轴上的 飞机的 。此外,他们还告诉我们 半径之和正好是 $$$m$$$$$$^{\text{*}}$$$。

请求整数点数 内部或边界上 至少一圈。正式地,该问题定义如下。

给定一个整数序列 $$$x_1,x_2,\ldots,x_n$$$ 和一个正整数序列 $$$r_1,r_2,\ldots,r_n$$$,其中已知 $$$\sum_{i=1}^n r_i = m$$$。

您必须计算满足以下条件的整数对 $$$(x,y)$$$ 的数量。

  • 存在一个索引 $$$i$$$ 使得 $$$(x-x_i)^2 + y^2 \le r_i^2$$$ ($$$1 \le i \le n$$$)。

$$$^{\text{*}}$$$这些信息真的有用吗?别问我;我真的不知道。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le m \le 2\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$x_1,x_2,\ldots,x_n$$$ — 圆心 ($$$-10^9 \le x_i \le 10^9$$$)。

每个测试用例的第三行包含 $$$r_1,r_2,\ldots,r_n$$$ - 圆的半径 ($$$1 \le r_i$$$, $$$\sum_{i=1}^n r_i = m$$$)。

保证 所有测试用例 $$$m$$$ 的总和 不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上输出满足条件的整数点数。

示例

输入
复制

4
2 3
0 0
1 2
2 3
0 2
1 2
3 3
0 2 5
1 1 1
4 8
0 5 10 15
2 2 2 2

输出
复制

13
16
14
52

注意

在第一个测试用例中,$$$r_1=1$$$ 的圆完全位于 $$$r_2=2$$$ 的圆内。因此,你只需计算后者内部的整数点数即可。有 $$$13$$$ 整数点使得 $$$x^2+y^2 \le 2^2$$$,所以答案是 $$$13$$$。

在第二个测试用例中,$$$r_1=1$$$ 的圆不完全位于 $$$r_2=2$$$ 的圆内。还有 $$$3$$$ 个额外点位于第一个圆内,但不在第二个圆内,因此答案为 $$$3+13=16$$$。