B - 円錐 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

3次元空間( xyz 空間)上に N 個の円錐が互いに重なり合わないように浮いています。

どの円錐も底面が yz 平面と平行で、x 軸の正の方向にとがっています。

i 番目の円錐の底面の中心の x 座標の値は X_i で半径は R_i 、高さは H_i です。

以下のクエリに Q 個答えてください。

  • 2 つの整数 A と B が与えられるので A ≦ x ≦ B となる空間の内いずれかの円錐の内側にある部分の体積をもとめよ。

制約

  • 与えられる数字はすべて整数
  • 1 ≦ N ≦ 100
  • 1 ≦ Q ≦ 10^5
  • 0 ≦ X_i ≦ 10^4
  • 1 ≦ H_i ≦ 10^4
  • 1 ≦ R_i ≦ 10^3
  • 0 ≦ A_i ≦ B_i ≦ 2×10^4

入力

入力は以下の形式で標準入力から与えられる。

N Q
X_1 R_1 H_1
X_2 R_2 H_2
:
X_N R_N H_N
A_1 B_1
A_2 B_2
:
A_Q B_Q
  • 1 行目には円錐の個数を表す整数 N とクエリの個数を表す整数 Q が空白区切りで与えられる。
  • 2 行目からの N 行のうち i 行目には i 番目の円錐の底面の中心の x 座標の値を表す整数 X_i と半径の長さを表す整数 R_i、高さを表す整数 H_i が空白区切りで与えられる。
  • N+2 行目からの Q 行のうち i 行目には i 番目のクエリの内容を表す整数 A_i, B_i が空白区切りで与えられる。

出力

出力は Q 行からなる。 i 行目には i 番目のクエリの答えを 1 行で出力せよ。 出力は絶対誤差または相対誤差が 10^{-3} 以下であれば許容される。 なお、出力の末尾に改行を入れること。

入力例1

10 10
3 3 3
2 1 1
5 2 3
1 5 6
2 9 3
4 6 12
11 18 5
4 15 25
0 2 3
1 1 7
0 1
0 2
0 10
3 10
0 100
3 8
1 5
2 9
3 4
6 9

出力例1

8.843002
80.992182
4173.878112
3865.997282
8512.668894
2882.971997
1227.377293
3629.490541
114.081013
1747.545749

入力例2

5 5
5 10 10
4 100 100
3 1000 1000
2 1000 1000
1 1000 1000
0 3
2 1000
4 314
3 217
5 432

出力例2

9409079.422279
3139502408.531295
2100737789.465234
1613523459.243475
2532621914.444282