0

私はlightoj裁判官からこの問題を解決していました（リンクを提供して申し訳ありませんが、写真を追加する方法がわかりません）.

コード

  #include <bits/stdc++.h>
  using namespace std;
  int main() {

   int t,temp;
   cin>>t;
   temp=t;
   while(t--)
   {
    double ab,ac,bc,r;
    cin>>ab>>ac>>bc>>r;
    double sq=ab*sqrt((r/(r+1)*1.0));
    printf ("Case %d: %lf\n", temp-t,sq);
   }
    return 0;
 }

しかし、問題は、この質問がバイナリ検索/二分法とマークされており、バイナリ検索でこれを行う方法を見つけることができなかったことです。これを行う方法を知るためにWebを検索しましたが、方法が見つかりませんでした. 二分探索/二分探索でこれを行うのを手伝ってくれる人はいますか? 二分探索/二分探索(検索を除く)を適用できる一般的な質問は何ですか?

4

1 に答える 1

1

同様の三角形を使用して、項 AD と AB を含む比率 ADE/ABC の式を見つけることができます。したがって、ABC = ADE + BDEC を代入して ADE/BDEC の比率を求めるのは簡単です。

AD は 0 < AD <= AB で制限されることがわかっています。次に、二分法を使用して、AD のどの値が上記の間隔の比率を満たすかを見つけることができます。(二分法の追加の読み物: https://mat.iitm.ac.in/home/sryedida/public_html/caimna/transcendental/bracketing%20methods/bisection/bisection.html )

これを解決するには、AD の正確な解が方程式の根を生成するように方程式を定式化する必要があります。そのような方程式の 1 つ: f(x) = ratio_act - ratio_est

// ADE/ABC = (AD/BC)^2 (By similar triangles)
// ADE/BDEC = (AD^2)/(AB^2 - AD^2)
double bisection(double AB, double ratio_act)
{
    auto f = [](double AD_est, double AB, double ratio_act){ return ratio_act - ((AD_est* AD_est/(AB*AB - AD_est*AD_est)));};
    double b = AB +1, a = 0, ratio_est, AD_est;
    cout << f(a, AB, ratio_act) * f(b, AB, ratio_act) << endl;
    do {
        AD_est = (b+a)/2;
        // as per above formula
        ratio_est = f(AD_est, AB, ratio_act);
        if (ratio_est*f(a, AB, ratio_act) < 0) {
            b = AD_est;
        } else {
            a = AD_est;
        }
    } while (abs(ratio_est - ratio_act) <= 1e-9);
    return AD_est;
}
于 2015-05-18T06:02:50.237 に答える