K - Hundred Eyes Monster Editorial /

Time Limit: 1 sec / Memory Limit: 256 MB

配点 : 300 点

あらすじ

私は召喚術を使う魔術師である。スケッチブックに描いた魔物の絵を実体化させることができる。

この度、京都大学霊長類研究所から百目おばけを召喚してほしいという依頼が届いた。

京都大学の霊長類学の発展に寄与できるなど何たる譽れであろうか！私は腕によりをかけて、飛び切り高品質な百目を作ることにした。

私はまず額と口を描いた。次はこの額と口の間になるべく多くの目を描こう。ふふ、百目の完成が楽しみだ。

問題文

2 次元平面上に 2 つの円 A, B がある。 円 A の中心の座標は (x_A, y_A), 半径は r_A であり、 円 B の中心の座標は (x_B, y_B), 半径は r_B である。 この 2 つの円の内部や外周は共通部分を持たない。 ここで、以下の条件を満たす円集合 S を考える。

  • S に含まれる任意の円は、A, B に接し、内部に共通部分を持たない。
  • S に含まれる任意の異なる円 C_1, C_2 は、内部に共通部分を持たない。

集合 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
テストケース 1 つは以下の形式で与えられる。 
x_A y_A r_A x_B y_B r_B

出力

出力は T 行からなる。 i (1 \leq i \leq T) 行目には i 番目のテストケースにおける S の要素数の最大値を出力せよ。

入力例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 つ目のテストケースでは、例えば以下のように配置すればよい。

Score : 300 points

Story

I am a Summoner who can invoke monsters. I can embody the pictures of monsters drawn on sketchbooks.

I recently have received a request from Primate Research Institute of Kyoto University to invoke "Hundred Eyes Monster".

What an great honor it is to contribute to the prosperity of the primate research of Kyoto University! I decided to paint an extremely high-quarity monster to the best of my ability.

I have already painted the forehead and mouth and this time I am going to paint as many eyes as possible between the forehead and mouth. Well...I cannot wait to see the complete painting.

Problem Statement

Two circles A, B are given on a two-dimensional plane. The coordinate of the center and radius of circle A is (x_A, y_A) and r_A respectively. The coordinate of the center and radius of circle B is (x_B, y_B) and r_B respectively. These two circles have no intersection inside. Here, we consider a set of circles S that satisfies the following conditions.

  • Each circle in S touches both A and B, and does not have common points with them inside the circle.
  • Any two different circles in S have no common points inside them.

Write a program that finds the maximum number of elements in S.

Constraints

  • 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
  • All values given as input are integers.
  • It is guaranteed that, when the radiuses of A and B change by 0.0005, the answer does not change.

Input

The input consists of multiple test cases and is given from Standard Input in the following format: 

T
testcase_1
:
testcase_T
Each test case is given with the following format. 
x_A y_A r_A x_B y_B r_B

Output

The output consists of T lines. On line i (1 \leq i \leq T), putput the maximum number of elements in S in i-th test case.

Sample Input 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

Sample Output 1

3
10
21
180
You can arrange circles ,for example, like the following images in Sample 1, 2.

Source Name

KUPC2016