AtCoder Regular Contest 052 B - 円錐
問題URL
解法
個のクエリについて、すべての円錐がどの程度区間に入っているか調べることができます。
ある円錐がある区間にどの程度入っているか求める方法を考えてみます。
区間の左端を、右端を
とします。
また、円錐の底面のx座標を、高さを
、底面の半径を
とします。
また、円錐の体積を
とします。
まずはじめに、 または
であるようなものは、区間の中に円錐が入っていないので、区間と円錐が共有する体積は
です。
また、
のように円錐を丸々覆ってしまうような区間の場合は区間と円錐が共有する体積は
です。
次に、のように、円錐の先の方だけ区間に含まれる場合について注目します。この場合、区間に含まれる図形は、元の円錐と相似であり、その相似比は 、
です。体積比は相似比の3乗の比なので、先の方だけ含まれる円錐については、その体積は、
になります。
次に、[tex;A \leqq x \lt B, B \lt x + h]のように、円錐の先の方だけ区間に含まれない場合について注目します。この場合、区間からはみ出る図形は、元の円錐と相似であり、その相似比は、
です。体積比は相似比の3乗の比になるので、はみ出た部分の体積は
です。
元の円錐からはみ出た区間を引けばよいので、区間と共有する体積はです。
最後に、のように、区間を覆うような円錐の場合を考えます。
これは、円錐の中でより体積を求め、そこから
より大きいはみ出た部分を引くことで得られます。
今まで求めてきた場合分けと同じように求めると、共有する体積はとなります。
以上をで全てのケースを列挙できているので、それぞれ計算して総和を出せば解けます。計算量はです。
ACしたコード
#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; } }