Вовлечение бинарного поиска / деления пополам в этом?
я делал Эта проблема от судьи lightoj (извините за предоставление ссылок, я не знаю, как добавить изображения). Это вопрос, основанный исключительно на геометрии, и мой appoarch был тем, что привело к Принятому решению.
Код
#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;
}
Но проблема в том, что этот вопрос был помечен как «бинарный поиск», и я не смог найти способ сделать это с помощью бинарного поиска. Я искал в Интернете, чтобы узнать, как это сделать, но не смог найти способ.Кто-нибудь может мне помочь сделать это с помощью бинарного поиска / деления пополам и каков общий вопрос, в котором мы можем применить разделение на две части / двоичный поиск (кроме поиска)
Решение
Используя похожие треугольники, мы можем найти формулу отношения ADE / ABC, включающую в себя члены AD и AB. Затем тривиально найти соотношение ADE / BDEC, подставив ABC = ADE + BDEC.
Мы знаем, что AD ограничен 0 < ОБЪЯВЛЕНИЕ <= 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;
}
Другие решения