涉及二进制search/bisection这个？

Question

我在 lightoj judge 做 this problem（很抱歉给了我不知道如何添加图片的链接）。这是纯粹的基于几何的问题，我的方法是这个导致接受的解决方案。

代码

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

但问题是这个问题被标记为二进制 searched/bisection 而我找不到用二进制 search.I 来做这个的方法 search.I 在网上搜索知道如何做但是找不到任何人都可以帮我用二进制 search/bisection 做这个吗？我们可以应用哪些一般问题 bisectioning/binarysearch（搜索除外）

Answer 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 的精确解产生方程的根。一个这样的等式是： 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;
}

涉及二进制search/bisection这个？

Involvement of binary search/bisection in this?

c++

binary-search

bisection