题解：SP4871 BRI - Bridge

· · 题解

参考资料

解题思路

根据光学知识，光线通过一段平行介质后与原来平行，所以前后两段路长可以一起计算。

设桥的水平宽度为 x，桥的竖直宽度（河的宽度）为 y，则桥长为：

\sqrt{x^2+y^2}

剩余部分的水平宽度为 a+b，垂直宽度为 c-x，则路长为：

\sqrt{(a+b)^2+(c-x)^2}

因此总花费为：

f(x)=s_2\sqrt{x^2+y^2}+s_1\sqrt{(a+b)^2+(c-x)^2}

求导可知 f(x) 是一个单峰函数，可以用 三分法 求 f(x) 的最小值。

f'(x)=\frac{s_2x}{\sqrt{x^2+y^2}}+\frac{s_1(x-c)}{\sqrt{(a+b)^2+(c-x)^2}}

我开始考虑用 斯涅尔定律 推导公式，但方程两边都带有三角函数，无法直接求解。

参考代码

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-10;
int a,b,c,h,s1,s2;
double f(double x)
{
    return s1*sqrt((a+b)*(a+b)+(c-x)*(c-x))+s2*sqrt(h*h+x*x);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a>>b>>c>>h>>s1>>s2;
        double l=0,r=c;
        while(r-l>eps)
        {
            double m1=(l*2+r)/3,m2=(l+r*2)/3;
            if(f(m1)<f(m2))r=m2;
            else l=m1;
        }
        cout<<fixed<<setprecision(2)<<f(l)<<'\n';
    }
    return 0;
}