【题解】UVA1356 Bridge

UVA1356 Bridge

在一条长度为 $B$ 的线段 $l$ 上，等距离截取一些点（包括左右端点），令点数为 $n$，相邻两个端点间距离为 $d\ (d \le D)$。每个端点处都作一条长度为 $H$ 的线段垂直于 $l$。相邻线段之间都存在一条全等的抛物线，抛物线总长为 $L$，令其最低点与 $l$ 的距离为 $h$。给定 $D,H,B,L$，求在 $n$ 最小时 $h$ 的值。
满足 $B \le L$

$\texttt{Solution}$

本题积分柿子均可能有错误，本人概不负责

具体柿子意会即可，等菜鸡 $\texttt{CXY07}$ 多学一点东西再回来改。

要求 $n$ 最小，显然有：

$$n=\lceil \dfrac{B}{D} \rceil\ ,\ d=\dfrac{B}{n}$$

令 $l_0$ 为每一条抛物线的长度，那么显然 $l_0=\dfrac{L}{n}$。

不难发现，$l_0$ 随着 $h$ 的增大而减小，可以感性理解一下。那么我们可以选择二分 $h$ 的值，通过判断抛物线总长与 $L$ 的大小关系来求解。

由于所有抛物线全等，则不妨设一个抛物线的顶点为 $(0,0)$，那么显然他过 $(-\dfrac{d}{2},H-h),(\dfrac{d}{2},H-h)$。

然后可以求出抛物线解析式:

$$y=\dfrac{4(H-h)}{d^2} x^2$$

现在需要求的便是 $x\in [-\dfrac{d}{2},\dfrac{d}{2}]$ 时，抛物线的长度。不难发现这等于 $x\in [0,\dfrac{d}{2}]$ 时的长度的 $2$ 倍。

考虑积分。可以考虑利用类似勾股定理的方法，有柿子：

$$ 2\times \int_0^{\frac{d}{2}} \sqrt{(dx)^2+(dy)^2}$$

如果令 $\dfrac{4(H-h)}{d^2}=a$ 的话，有 $y=ax^2$，且 $dy=y' \times dx$，$y'=2ax$。

那么可以写成：

$$ 2\times \int_0^{\frac{d}{2}} \sqrt{1+(2ax)^2} \ dx$$

所以我们需要积的函数是 $f(x)=\sqrt{1+4a^2x^2}$。

直接上自适应辛普森积分法即可。