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)$ 是一个单峰函数，可以用三分法求 $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;
}