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