AtCoder Regular Contest 052 B - 円錐

問題
http://arc052.contest.atcoder.jp/tasks/arc052_b

3次元空間上にN個の円錐が互いに重なり合わないように存在する。
それぞれの円錐はYZ平面に垂直に浮かんでいる。
M個の区間のクエリ(L[i], R[i])が与えられる。
各クエリに対して、2平面X = L[i], X = R[i]で囲まれる空間と円錐との共有部分の体積を求めよ。

解法
O(NQ)解法
各クエリに対して、N個の円錐の体積を足し合わせる。
X = L[i]以上で切った円錐の体積を足す。
X = R[i]で切れる体積は切れた上部を引く。
半径R[i]の円錐の高さH[i]を、円錐の切った上部の体積の計算は、
長さの比率の3乗は体積の比率になることから、高さの比率を3乗して元の円錐の体積に掛けると良い。

ll X[111], R[111], H[111];
double V[111];
 
double calc(int i, ll from) {
  const double h = X[i] + H[i] - from;
  const double ratio = h / H[i];
  return V[i] * ratio * ratio * ratio;  // 体積比
};
 
int main() {
  int N, Q; cin >> N >> Q;
  rep(i, N) cin >> X[i] >> R[i] >> H[i];
  rep(i, N) V[i] = acos(-1) * R[i] * R[i] * H[i] / 3.0;
 
  while(Q--) {
    ll L, R; cin >> L >> R;
    double res = 0.0;
    rep(i, N) {
      if(L <= X[i] + H[i]) res += calc(i, max(L, X[i]));
      if(R <= X[i] + H[i]) res -= calc(i, max(R, X[i]));
    }
    printf("%.10f\n", res);
  }
  return 0;
}