分数: 300 点
故事
我是一名可以召唤怪物的召唤师。我可以将素描本上画的怪物图画具体化。
最近,我收到京都大学灵长类研究所发出的“百眼怪物”调用请求。
能为京都大学灵长类动物研究的繁荣做出贡献是多么荣幸! 我决定尽我所能,画出一个品质极高的怪物。
我已经画了额头和嘴巴,这次我要在额头和嘴巴之间画尽可能多的眼睛。 嗯……我迫不及待地想看到完整的画作。
问题陈述
两个圆圈 A, B 在二维平面上给出。 圆心和半径的坐标 A 是 ( 分别为x_A, y_A)和 r_A 。 圆心和半径的坐标 分别为 B 是 ( 分别为x_B, y_B)和 r_B 。 这两个圆内部没有交点。 在这里,我们考虑一组圆 S 满足以下条件。
- 中的每个圆圈 S 触及两者 A 和 B,并且与圆内的它们没有共同点。
- 中任意两个不同的圆圈 S 内部没有共同点。
编写一个程序,查找 中元素的最大数量 S.
约束
- 1 \leq T \leq 50000
- -10^5 \leq x_A \leq 10^5
- -10^5 \leq y_A \leq 10^5
- -10^5 \leq x_B \leq 10^5
- -10^5 \leq y_B \leq 10^5
- 1 \leq r_A \leq 10^5
- 1 \leq r_B \leq 10^5
- {r_A}^2 + {r_B}^2 < (x_A - x_B)^2 + (y_A - y_B)^2
- 作为输入给出的所有值都是整数。
- 可以保证,当半径 A 和 B 更改为 0.0005,答案不变。
输入
输入由多个测试用例组成,并由标准输入以以下格式给出:
T testcase_1 : testcase_T每个测试用例都按以下格式给出。
x_A y_A r_A x_B y_B r_B
输出
输出包括 T 行。 上线 i (1 \leq i \leq T), 输入最大元素数 S in i- 第一个测试用例。 总共
示例输入 1
4 0 -3 2 0 3 2 0 0 9 8 8 2 0 0 9 10 10 5 0 0 707 1000 1000 707
示例输出 1
3 10 21 180您可以排列圆圈,例如示例 1、2 中的以下图像。