Skip to main content

SP4871 BRI - Bridge

· 2 min read

参考资料​

解题思路​

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

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

x2+y2\sqrt{x^2+y^2}

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

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

因此总花费为：

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

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

f′(x)=s2xx2+y2+s1(x−c)(a+b)2+(c−x)2f'(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;
}