题解：P6894 [ICPC2014 WF] Crane Balancing
wangyizhi
·
·
题解
写在最前面
%%% 膜拜楼上巨佬 %%%
这篇题解的思路与楼上大佬相近，但感觉楼上大佬公式讲的不是很清楚（对 OIers 而言），于是本蒟蒻决定把公式推导一下 QwQ。
0.说明
可能的前置知识：
-
向量运算
-
三点共线定理
-
物体的平衡条件（力矩平衡）
下文中记原点为 O。
1.求重心
对于重心，先考虑把多边形剖成小三角形求重心，然后根据它们的质量进行合并。
1.1 求三角形重心
考虑 \triangle ABC，记其重心为 G，如何用 \overrightarrow{OA}、\overrightarrow{OB}、\overrightarrow{OC} 表示 \overrightarrow{OG}？
记 BC 中点为 D，则 G 在线段 AD 上且满足 AG=2DG。由于 B、C、D 三点共线且 BD=CD，则有
\overrightarrow{OD}=\frac{1}{2}\overrightarrow{OB}+\frac{1}{2}\overrightarrow{OC}
又由于 A、G、D 三点共线且 AG=2DG，则有
\overrightarrow{OG}=\frac{2}{3}\overrightarrow{OD}+\frac{1}{3}\overrightarrow{OA}
综合两式，得
\overrightarrow{OG}=\frac{1}{3}\overrightarrow{OA}+\frac{1}{3}\overrightarrow{OB}+\frac{1}{3}\overrightarrow{OC}
1.2 求三角形质量
考虑 \triangle ABC，由题意得其质量可以表示为 S_{\triangle ABC}。由“二维向量叉积”（注：其实并没有这个概念，，，叉积其实只有三维向量有，，，）的几何意义得
m=S_{\triangle ABC}=\frac{1}{2}\overrightarrow{AB}\times \overrightarrow{AC}
1.3 合并两个多边形时的重心变化
记要合并的第一个多边形质量为 m_1，重心为 G_1，第二个多边形质量为 m_2，重心为 G_2，合并后的重心为 G。
由重心的定义，当合并后以 G 为参考点时，合力矩为 0。因此有
m_1\overrightarrow{GG_1}=m_2 \overrightarrow{GG_2}
即
\frac{m_2}{m_1}=\frac{\overrightarrow{GG_1}}{\overrightarrow{GG_2}}
由三点共线定理，又有
\overrightarrow{OG}=\frac{1}{m_1+m_2}(m_1\overrightarrow{OG_1}+m_2\overrightarrow{OG_2})
当有多个多边形时，同理可以得出
\overrightarrow{OG}=\frac{1}{m_1+m_2+m_3+...}(m_1\overrightarrow{OG_1}+m_2\overrightarrow{OG_2}+m_3\overrightarrow{OG_3}+...)
因此我们就可以把物体的重心位置和质量求出来啦。
2.求答案
设支撑面为 l\sim r，重心所在横坐标为 x_0，起重机质量为 m_0，第一个点的坐标为 (x,y)，挂的物体的质量为 m。
分情况讨论：
a) x_0>r
(r-x)\times m_{min}=(x_0-r)\times m_0
即
m\ge \frac{x_0-r}{r-x}m_0
- 若 x<l，则最小值时以 (r,0) 为参考点平衡，最大值时以 (l,0) 为参考点平衡，因此
(r-x)\times m_{min}=(x_0-r)\times m_0
(l-x)\times m_{max}=(x_0-l)\times m_0
即
\frac{x_0-r}{r-x}m_0\le m \le\frac{x_0-l}{l-x}m_0
b) x_0<l
求法同 a），不再赘述。
c) l\le x_0\le r
- 若 x>r，则最大值时以 (r,0) 为参考点平衡。因此有
(r-x_0)\times m_0=(x-r)\times m_{max}
即
m\le \frac{r-x_0}{x-r}m_0
m\le \frac{x_0-l}{l-x}m_0
- 若 l\le x \le r，则无论如何都会平衡。
OK，那到这里这个问题我们就推完了，剩下的就是代码实现的问题了。
代码就不放了，看楼上大佬的吧。