AtCoder Regular Contest 052 B - 円錐

問題URL

B - 円錐

解法

個のクエリについて、すべての円錐がどの程度区間に入っているか調べることができます。
ある円錐がある区間にどの程度入っているか求める方法を考えてみます。
区間の左端を、右端をとします。
また、円錐の底面のx座標を、高さを、底面の半径をとします。 また、円錐の体積をとします。
まずはじめに、 または であるようなものは、区間の中に円錐が入っていないので、区間と円錐が共有する体積はです。 また、のように円錐を丸々覆ってしまうような区間の場合は区間と円錐が共有する体積はです。

次に、のように、円錐の先の方だけ区間に含まれる場合について注目します。この場合、区間に含まれる図形は、元の円錐と相似であり、その相似比は 、 です。体積比は相似比の3乗の比なので、先の方だけ含まれる円錐については、その体積は、になります。

次に、[tex;A \leqq x \lt B, B \lt x + h]のように、円錐の先の方だけ区間に含まれない場合について注目します。この場合、区間からはみ出る図形は、元の円錐と相似であり、その相似比は、 です。体積比は相似比の3乗の比になるので、はみ出た部分の体積はです。
元の円錐からはみ出た区間を引けばよいので、区間と共有する体積はです。

最後に、のように、区間を覆うような円錐の場合を考えます。
これは、円錐の中でより体積を求め、そこからより大きいはみ出た部分を引くことで得られます。
今まで求めてきた場合分けと同じように求めると、共有する体積はとなります。

以上をで全てのケースを列挙できているので、それぞれ計算して総和を出せば解けます。計算量はです。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

long double pi = 3.14159265359;

int main()
{
    int N,Q;cin >> N >> Q;
    vector<pair<pair<int, int>, pair<int, double>>> v;
    for(int i = 0;i < N;i++){
        int x,r,h;cin >> x >> r >> h;
        v.push_back(make_pair(make_pair(x, r), make_pair(h, pi * r * r * h * 1 / 3)));
    }
    for(int q = 0;q < Q;q++){
        long double ans = 0;
        int A,B;cin >> A >> B;
        for(int i = 0;i < N;i++){
            int x = v.at(i).first.first;
            int r = v.at(i).first.second;
            int h = v.at(i).second.first;
            double vo = v.at(i).second.second;
            if(A <= x && x + h <= B){
                ans += vo;
            }else
            if(x < A && A <= x + h && x + h <= B){
                ans += vo * pow(1.0*(x + h - A) / h, 3);
            }else
            if(A <= x && x < B && B < x + h){
                ans += vo - vo * pow(1.0*(x + h - B)/ h, 3);
            }else
            if(x <= A && B <= x + h){
                ans += vo * pow(1.0*(x + h - A) / h, 3) - vo * pow(1.0*(x + h - B) / h, 3);
            }
        }
        cout<<setprecision(20)<<ans<<endl;
    }
}