← 返回题目列表

AtCoder · arc052_b

B. 锥体

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

問題文

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 第 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