date: 2020-07-18 12:00~17:00

2020-2021 BUAA ICPC Team Supplementary Training 01

2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

现有 $n$ 个质量均匀分布的棒子，头在 (0, 0) 点挂着，尾在 (L, 0) 点挂着，然后让整条链自然下垂，求每个点自然下垂稳定之后的位置。

题解：

不会奇奇怪怪的东西，我只知道自然下垂时，必然总体的重力势能是最小的。

记长度单位为米，棒子每米的质量为 $m_0$，重力势能为 $g$。

记 $\alpha_i \in [0, \pi]$ 为第 $i$ 个棒子和重力方向的夹角。写出来每个点的坐标，写一下重力势能，限制一下最后一个点的坐标为 $(L, 0)$，用拉格朗日乘数法，我们需要最小化： $$ P\left(\vec{\alpha}, \lambda'_1, \lambda'_2\right) = \left(\sum_{i=1}^n{-m_0 l_i g \left(\frac{1}{2} l_i \cos{\alpha_i} + \sum_{j<i}{l_j \cos{\alpha_j}} \right)}\right) + \lambda'_1 \left(\left(\sum_{i=1}^n{l_i \sin{\alpha_i}}\right) - L\right) + \lambda'_2 \left(\sum_{i=1}^n{l_i \cos{\alpha_i}}\right) $$ 相当于最小化： $$ F\left(\vec{\alpha}, \lambda_1, \lambda_2\right) = \left(\sum_{i=1}^n{-l_i \left(\frac{1}{2} l_i \cos{\alpha_i} + \sum_{j<i}{l_j \cos{\alpha_j}} \right)}\right) + \lambda_1 \left(\left(\sum_{i=1}^n{l_i \sin{\alpha_i}}\right) - L\right) + \lambda_2 \left(\sum_{i=1}^n{l_i \cos{\alpha_i}}\right) $$ 偏导： $$ \begin{array}{rcl} \frac{\partial F}{\partial \alpha_i} &=& \frac{1}{2} l_i^2 \sin{\alpha_i} + \sum_{j > i}{l_j l_i \sin{\alpha_i}} + \lambda_1 l_i \cos{\alpha_i} - \lambda_2 l_i \sin{\alpha_i} \\ &=& l_i \sin{\alpha_i} \left(\frac{1}{2} l_i + \sum_{j > i}{l_j}\right) + \lambda_1 l_i \cos{\alpha_i} - \lambda_2 l_i \sin{\alpha_i} \end{array} $$ $$ \frac{\partial F}{\partial \lambda_1} = \left(\sum_{i=1}^n{l_i \sin{\alpha_i}}\right) - L \\ \frac{\partial F}{\partial \lambda_2} = \sum_{i=1}^n{l_i \cos{\alpha_i}} $$

目标是让偏导都为 $0$，但容易想到实际上偏导均为 $0$ 应该是有两个解。另外一个是取最大值，那种情况下必然 $\alpha_1 > \frac{\pi}{2}$。所以我们限制一下 $\alpha_1 \in [0, \frac{\pi}{2}]$。

考虑一下 $\alpha_{i} > \alpha_{i+1}$，容易发现如果我们将第 $i$ 个棒子的起点和第 $i+1$ 个棒子的终点用线段连起来，会发现两个棒子都在这个线段的上方，但是我们如果让两个棒子根据这个线段对称一下，就能得到重力势能最小的解。因此在最小化重力势能的情况下 $\alpha_{i} \le \alpha_{i+1}$。

记 $x_i$ 为： $$ x_i = \frac{1}{2} l_i + \sum_{j > i}{l_j} $$ $x_i$ 的差分是两个棒子长度和的一半，所以 $x_i$ 单调递减。

我们先令 $\frac{\partial F}{\partial \alpha_i} = 0$，容易发现只要前两个角度不同，就可以直接解出 $\lambda_1$ 和 $\lambda_2$。

假设 $\alpha_1 < \alpha_2$ （即 $\alpha_1 \ne \alpha_2$），有： $$ \lambda_1 = \frac{\left|\begin{array}{ccc} -x_1 \sin{\alpha_1} & -\sin{\alpha_1} \\ -x_2 \sin{\alpha_2} & -\sin{\alpha_2} \\ \end{array}\right|} {\left|\begin{array}{ccc} \cos{\alpha_1} & -\sin{\alpha_1} \\ \cos{\alpha_2} & -\sin{\alpha_2} \\ \end{array}\right|} = \frac{\sin{\alpha_1}\sin{\alpha_2} \left(x_1 - x_2\right)}{\sin{(\alpha_1 - \alpha_2)}} $$ $$ \lambda_2 = \frac{\left|\begin{array}{ccc} \cos{\alpha_1} & -x_1 \sin{\alpha_1} \\ \cos{\alpha_2} & -x_2 \sin{\alpha_2} \\ \end{array}\right|} {\left|\begin{array}{ccc} \cos{\alpha_1} & -\sin{\alpha_1} \\ \cos{\alpha_2} & -\sin{\alpha_2} \\ \end{array}\right|} = \frac{x_1 \sin{\alpha_1} \cos{\alpha_2} - x_2 \cos{\alpha_1} \sin{\alpha_2}}{\sin{(\alpha_1 - \alpha_2)}} $$

利用 $\frac{\partial F}{\partial \alpha_i} = 0$，可以解得 $\alpha_i$ 是以 $-\lambda_1$ 为对边、以 $x_i - \lambda_2$ 为临边的直角三角形中的角，可以用 atan2 来解。因为 $x_i$ 是单调递减的，所以这样直接解出来的角度也是单调递增的。

到现在我已经分析的是头昏眼花，所以接下来的只能猜一下了。想象一下，如果 $\alpha_1$ 固定了，那么随着 $\alpha_2$ 的变化，我们通过上面的方式计算一下最后一个点的坐标，这个点划过的轨迹必然是一个连续、光滑的曲线，我们需要一个可以三分的目标函数，这个目标函数越小，就表明最终一个点越接近 $(L, 0)$。

最后就只能各种距离函数都试一下了 XwX，不过确实轨迹上的曲率很难确定，而且轨迹是光滑的，因此像切比雪夫距离、曼哈顿距离之类的，在确定的距离下图形不是光滑的距离函数会比较适合。 最后发现三分第一个角套三分第二个角，最小化最终一个点到 $(L, 0)$ 的切比雪夫距离能获得正确的解，晚安。

哦天哪，我们先考虑一下解出来的 $\lambda_2$ 的意义，由于 $-\lambda_1 \ge 0$，所以 $\lambda_2$ 相当于是在确定一个下标 $j$，使得： $$x_1 - \lambda_2 > x_2 - \lambda_2 > \cdots > x_j - \lambda_2 \ge 0 > x_{j+1} - \lambda_2 > \cdots > x_n - \lambda_2$$ 即 $\lambda_2$ 确定了什么时候角度会超过 $\frac{pi}{2}$，也即纵坐标开始往反方向走的时候。

来确定一下 $\lambda_2$ 和 $\alpha_2$ 的关系吧，有： $$ \lambda_2 = \frac{x_1 \sin{\alpha_1} \cos{\alpha_2} - x_2 \cos{\alpha_1} \sin{\alpha_2}}{\sin{(\alpha_1 - \alpha_2)}} = \frac{(x_1 - x_2) \sin{\alpha_1} \cos{\alpha_2}}{\sin{(\alpha_1 - \alpha_2)}} + x_2 \\ \frac{\partial \lambda_2}{\partial \alpha_2} = (x_1 - x_2) \sin{\alpha_1} \frac{-\sin{\alpha_2} \sin{(\alpha_1 - \alpha_2)} - \cos{\alpha_2} \cos{(\alpha_1 - \alpha_2)}}{\sin{(\alpha_1 - \alpha_2)}} = -(x_1 - x_2) \sin{\alpha_1} \frac{\cos{\alpha_1}}{\sin{(\alpha_1 - \alpha_2)}} \ge 0 $$ 即 $\lambda_2$ 随 $\alpha_2$ 的增大而单调递增，即是说第二个角度越大，纵坐标越是提早往反方向走。

而由于 $-\lambda_1$ 始终大于或等于 $0$，因此 $\sin{\alpha_i} \ge 0$，也即横坐标是持续增长的，不会转一圈又捞回来。

那么更重要的分析是确定一下最终一个点的纵坐标是否是随 $\alpha_2$ 的增大而持续增大的，再分析下去我就要死了，总之 $\cos{\alpha_i}$ 是前面一些是正的，后面一些是负的，我们假装用长度加权求和后是递增的好了 XwX。

那么容易想到如果 $\alpha_1$ 固定了，那么随着 $\alpha_2$ 的增长，最终那个点的纵坐标会先从负的，连续地变化到正的，那刚好我们可以用二分来求一下纵坐标为 $0$ 时的 $\alpha_2$。此时的横坐标也会和 $\alpha_1$ 有一个关系，至于是不是单调地连续变化，已经没有什么好害怕的了，猜一下吧，随 $\alpha_1$ 的增长是单调递增的，那么这一层也是可以二分的。

最终的做法就是二分 $\alpha_1$，求一下 $\alpha_2$ 是多少是最终的点的纵坐标为 $0$，二分找最终点横坐标为 $L$ 的 $\alpha_1$；对于 $\alpha_2$ 的求法，也是二分一下，找最终点纵坐标为 $0$ 时的 $\alpha_2$。

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：