ARC 052 B

今回はこの問題。

arc052.contest.atcoder.jp

xyz空間上にn個の円錐が互いに重なり合わないように浮いています。どの円錐も底面がyz平面と平行で、x軸の正の方向にとがっています。i番目の円錐の底面の中心のx座標の値はx[i]、半径はr[i]、高さはh[i]です。2つの整数aとbが与えられるのでa<=x<=bとなる空間の内いずれかの円錐の内側にある部分の体積をもとめよ、というクエリがq個与えられるのでそれぞれ答えてください、という問題です。

回答はこちら。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    double pai = 4 * atan(1);
     
    double gettaiseki(double r, double h)
    {
        return pai * r * r * h / 3;
    }
     
    int main()
    {
        int n, q;
        cin >> n >> q;
        double x[101], r[101], h[101];
        double taiseki[20001];
        for(int i = 0; i < n; i++){
            cin >> x[i] >> r[i] >> h[i];
            taiseki[i] = gettaiseki(r[i], h[i]);
        }
        double result[20001] = {};
        // result[j] : 0 <= x <= jに含まれる部分の体積の和
        for(int ii = 1; ii <= 20000; ii++){
            for(int j = 0; j < n; j++){
                double i = ii + 0.0;
                if(x[j] >= i) continue;
                if(i >= h[j] + x[j]) result[ii] += taiseki[j];
                else result[ii] += (1 - pow((h[j] - i + x[j]) / h[j], 3.0)) * taiseki[j];
            }
        }
        for(int i = 0; i < q; i++){
            int a, b;
            cin >> a >> b;
            printf("%.10f\n", result[b] - result[a]);
        }
        return 0;
    }

さきに、0<=x<=i(i = 1, 2, ... 2 * 10^4)の範囲にある部分の体積の和を求めておきます。iが底面に達しないときと、頂点よりも上に来ているとき、そうでないときの3パターンに分けます。iが底面に達しなければ足さなければいいし、頂点よりも上であれば円錐全体の体積を足せばいいです。そうでないときは、(円錐全体の体積)-(含まれていないところの体積)を求めて足せばいいです。