1353 - Function of Euclidean Distance

問題

整数 $L$ と、実数 $X$ について、関数 $f(L,X)$ を以下のように定義します。

• $f(L, X) :=$ $(0 \leq x,y \leq L)$ を満たす全ての整数の組 $(x, y)$ のうち、 $2$ つの座標 $(0, 0),(x, y)$ 間のユークリッド距離が $X$ 以下であるものの個数。

なお、この問題での座標とは二次元座標平面上における座標のことを表します。

$2$ つの整数 $L, K$ が与えられるので、$f(L, X) \geq K$ を満たす最小の実数 $X$ を求めてください。

この問題では $1$ つの入力につき $T$ 個のテストケースが与えられるので、それら全てに答えてください。

入力

入力は以下の形式で標準入力から与えられる。入力の $1$ 行目は以下のとおりである。

$T$

$2$ 行目以降 $T$ 行にわたって $T$ 個のテストケースが与えられる。それぞれ以下の形式で与えられる。

$L$ $K$

出力

各テストケースについて $f(L,X) \geq K$ を満たす最小の実数 $X$ を出力せよ。また、各テストケースごとに改行をすること。
出力された値は、誤差が $10^{-5}$ 以下のとき正解とする。

制約

• $1 \leq T \leq 10^5$
• $0 \leq L \leq 10^3$
• $1 \leq K \leq (L+1)^2$
• 入力は全て整数である
• この制約上において、条件を満たす実数 $X$ が存在することは証明できる

部分点

この問題には部分点が設定されている。

• $T = 1$ を満たすデータセットに全て正解した場合、$60$ 点が与えられる。
• 追加制約のないデータセットに全て正解した場合、追加で $340$ 点が与えられ、合計で $400$ 点が得られる。

入出力例

入力例１

1
1 3

出力例１

1.000000

$(0 \leq x,y \leq 1)$ を満たす整数の組は、$\{0,0\},\{0,1\},\{1,0\},\{1,1\}$ の $4$ つであり、座標 $(0,0)$ と各座標とのユークリッド距離は以下の通りです。

• $(0,0): 0$
• $(0,1): 1$
• $(1,0): 1$
• $(1,1): 1.4142...$

そのため、$X = 1$ とすれば $f(L,X) = f(1,1) = 3 \geq 3$ となり、$f(L,X) \geq K$ を満たすことができます。また、これを満たす最小の実数は $1$ であるため、$1$ を出力すればよいです。
このケースは部分点の制約 $(T = 1)$ を満たします。

入力例２

3
1 4
10 1
1000 1002001

出力例２

1.414214
0.000000
1414.213562

このケースは部分点の制約 $(T = 1)$ を満たしません。