请问这个直线的方程怎么求

[ly90907]

如图所示，我有 n 个离散的点，一根直线从上方掉落，直到落到“最高”的两个点，（其实不一定是最高，就是这根直线无法再下落，重力势能最小了），然后根据这两个点求得直线方程。

想问下各位大帅逼 /大漂亮用什么算法，或者这个算法的关键词我自己搜索也行，十分感谢。

[Raven316]

@ly90907 https 代理的端口设置错了

[Mithril]

忽然发现你这题目确实有问题。。。如果是无质量的直线那么它必然过最高点。
但如果按你说的，可能如果不过最高点，就按你说的根据重力势能算，那就得考虑重心问题，它就不可能是直线。。。
@ly90907 比如你 8L 第一张图，如果右侧两个最高点之间的距离很远，那么蓝色线就是对的

[GuuJiang]

@GuuJiang 这题要有解，两侧必须是有界的，换句话说你想求的其实不是“直线”，而是线段，否则的话就以你在#8 发的那个反例来说，最开始的两个点在图里看起来不满足，但是只要往右边延伸足够长度，又变成满足的了，继续往右延伸，再次变成不满足，且正解变到了它们的右侧，所以必须要先定义范围

[zxCoder]

直线没办法

线段感觉稍微有点复杂，得看怎么定义这个重力势能

[zxCoder]

@zxCoder 不是直线没办法。。。是直线我想不出来，应该就是最高的前两个点了？

[stonewolfcjq]

找个最高点，再依次计算最高点和其他每一点连线的直线斜率，取绝对值最小的那个

[GuuJiang]

其实就是先求上凸包，然后在构成上凸包的各线段中取包含 m 的，必然会有一段或两段，如果只有一段即为所求，如果有两段说明 m 是它们的交点，此时结果取决于定义

[chairuosen]

9L 正解吧

[Jirajine]

按你的说法，首先假设线段长度远大于点的定义域 /值域范围，线段重心正好在定义域中点上下落。线段与点之间不考虑滑动（摩擦系数视为无限大）。
那么很简单了，首先最高点一定能取到，先取到最高点以后向线段重心所在方向旋转，碰到第一个点停止。判断重心是否在两点之间，如果不在就放弃第一个点，绕第二个点继续向重心方向旋转，直到重心在两点之间为止。

[aneureka]

@Jirajine #29 不一定能取到最高点吧，比如这种情况，绿线应该才是正解

（不知道图片能不能正常显示）

[ho121]

点不多的话，用穷举？

[Jirajine]

@aneureka #30 你没有看完我写的，假设是水平下落，第一个碰到的点一定是最高点。判断重心后再旋转。本质上是模拟下落的过程。

[L5411]

必须得计算线段的重力势能吧

[L5411]

@Jirajine 正解

[3dwelcome]

@aneureka 我觉得红线也挺符合条件的，汗。

[3dwelcome]

@aneureka "不知道图片能不能正常显示"

v2 回帖里显示图片，貌似只能是 v2 图库，sina 图库，imgur 这三个。
只有发帖不受任何限制，随便一个网络图片都可以。

[oamu]

找一条直线，其他点都在这条直线下面？那不是找出最大的两个值，两点式一算就出来了么。

[oamu]

@oamu 不对，想错了。找出最大值，然后两点式算斜率，取斜率绝对最小的吧，那应该每组数据都有一条或者两条这样的直线。

[aneureka]

@3dwelcome #35 哈哈确实 感觉还是得根据实际情况来 这个问题定义感觉不是太严谨 其实点不多的话用个 On^3 的循环扫一遍也就可以了

[GuuJiang]

总结下，首先“其他所有点都在直线之下”这个只是必要非充分条件，因为上凸包里的每一段所在的直线都是满足这个条件的，所以问题转化成了求上凸包里某一段所在的直线，关键在于这一段应该满足什么条件，上面有不少人说一定过最高点的，还有说斜率最小的，这两个都是不对的，反例都已经在#8 的图里给出来了
其实 LZ 你最开始描述问题的方式已经非常接近真相了，想象下这个物理过程，线落下来接触了一个线段以后为什么还会旋转，就是因为中心落在了线段之外，所以所求线段需要满足的条件已经很明显了，就是让重心落在内部，由于假设是质量均匀直线，所以重心自然就是中点(PS：就算题目换成质量不均匀的线段也可以用同样的方法求解，只需要换成真正的重心即可)
另外，相比起传统的求上凸包方法，针对这个问题可以做一些优化，起点只需要从最高点开始，并且根据重心位置只用考虑它的一侧，另一侧直接丢弃，另外过程中只需要碰到第一个包含了重心的线段就可以停止了，因为重心只可能包含在一个线段内（在交点的情况忽略）