はむへい’s diary

ねむいです。

AtCoder Regular Contest 052 B - 円錐

問題URL

B - 円錐

解法

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

次に、 x \lt A, A \lt x + h \leqq Bのように、円錐の先の方だけ区間に含まれる場合について注目します。この場合、区間に含まれる図形は、元の円錐と相似であり、その相似比は 、 元の円錐 : 区間に含まれる円錐 = h : x + h - Aです。体積比は相似比の3乗の比なので、先の方だけ含まれる円錐については、その体積は、 S * (x + h - A)^{3} / h^{3}になります。

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

最後に、x \lt A,B \lt x + h のように、区間を覆うような円錐の場合を考えます。
これは、円錐の中でAより体積を求め、そこからBより大きいはみ出た部分を引くことで得られます。
今まで求めてきた場合分けと同じように求めると、共有する体積は S * (x + h - A)^{3} / h^{3} -  S * (x + h - B)^{3} / h^{3}となります。

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

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;
    }
}