← 返回题目列表

AtCoder · kupc2016_k

K. 百眼怪物

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

分数: 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 中的以下图像。