题解：SP4871 BRI - Bridge

原题链接

• 洛谷 SP4871 BRI - Bridge

解题思路

本来想用 折射定律 推公式做的，但化简后方程两边都带有三角函数，作者太菜 解不出来，只能用三分答案。

光线通过一条平行的介质后会与原来平行，所以前后两段路可以一起计算。

设桥的水平宽度为 $x$，桥的垂直宽度（河的宽度）为 $k$，则桥长为 $\sqrt{x^2+k^2}$。

剩余部分的水平宽度为 $a+b$，垂直宽度 $c-x$，路长为 $\sqrt{(a+b)^2+(c-x)^2}$。

总费用为 $f(x)=s_2\cdot\sqrt{x^2+k^2}+s_1\cdot\sqrt{(a+b)^2+(c-x)^2}$。

这是一个单峰函数，用三分求 $f(x)$ 的极值点。

参考代码

#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 mid1=l+(r-l)/3;
			double mid2=r-(r-l)/3;
	        if(f(mid1)<f(mid2))r=mid2;
	        else l=mid1;
		}
		cout<<fixed<<setprecision(2)<<f(l)<<'\n';
	}
	return 0;
}