[bzoj 3695] 滑行

矩形区域 (0,0) - (x,y) 上有n个条形区域, 第i个宽度为hi, 在上面滑动的速率为vi. 路线自拟, 不能离开矩形区域, 求 (0,0) 到 (x,y) 的最短用时. (n≤100, x≤10^3, vi<v(i+1) for 1≤i<n)

疑惑: 如果光发生全反射, 题目该怎么解呢? 欢迎指教或讨论...... 一开始没有理解题意, 觉得我缺少重力加速度, 摩擦系数等一系列参量, 遂百度之. 理解了题意之后不小心看到了 "二分", "光路最短" 等字样......

根据初中物理知识 -_-b 可以联想到光线的折射. 记得入射角和折射角符合某个定律.

折射定律 1. 折射光线在入射面内. 2. 折射线和入射线分居法线两侧. 3. 入射角 和折射角 的正弦的比值, 对两种媒介是一个常数 其中 是媒介中的光速.

根据 "光路最短" 原理, 我们只需找出光从 (0,0) 到 (x,y) 通过的路径, 它由射出的方向唯一确定.

一个射出的角度对应矩形区域上边界的一个位置, 并且位置的横坐标关于角度单调. 不用担心跃出边界, 因为由于 , 轨迹是一道上凸的折线或一条直线. 我们二分求出角度, 最后计算时间.

为了避免三角函数反三角函数, 我直接二分角度的 值.

WA了一发, 二分的精度不够. 提高精度, 换用long double, 就AC了, 速度不错.

但是把long double换成double, 或者把精度改大就不行了......

全反射 ( 值大于 1) 这个肯定是会产生问题的......此时我的代码会对负数开根号, 返回NaN, 执行r=m. 的确, 改成if (w*k > x) r = m就WA掉了......

typedef long double ld;
const int N = 100;
int h[N], v[N];
int main()
{
	int n, x, y = 0;
	scanf("%d%d", &n, &x);
	rep (i, 0, n) scanf("%d", h+i), y += h[i];
	rep (i, 0, n) scanf("%d", v+i);
	ld l = 0, r = x/sqrt((ld)x*x + y*y);
	while (r-l > 1e-12)
	{
		ld m = (l+r)/2, w = 0, k = m/v[0], k2 = k*k;
		rep (i, 0, n) w += h[i] * v[i] / sqrt(1 - k2*v[i]*v[i]);
		if (w*k < x) l = m;
		else r = m;
	}
	l = (l+r)/2;
	ld t = 0, k = l/v[0], k2 = k*k;
	rep (i, 0, n) t += h[i] / (v[i] * sqrt(1 - v[i]*v[i]*k2));
	printf("%.3f\n", (double)t);
	return 0;
}