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

[ly90907]

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

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

[HaydenYe]

先找最高点 然后绕最高点旋转？ 第一次相交情况就是吧（顺逆时针都可以 然后取低值）

[Raven316]

所以图呢。。

[qqq8724]

@Raven316 要魔法上网

[marcong95]

找出来两个极值连一条线？

不过这个重力势能是不是有点难定义，例如我在两点直接直接戳一条平行于 y 轴的直线，那算不算？

[inertia]

@HaydenYe 不一定会在最高点上，比如你可以随便找个带阻尼的正弦函数试试

[codehz]

这样描述的话，听起来会有很多边界问题，怎么判定最高，举个例子
4 个数据点
2 4 1 2
是选择 1 2 点连线还是 2 4 点呢

[lance6716]

凸包

[ly90907]

@Raven316 啊，看不到吗？我还专门预览过 https://imgur.com/ntO2HZS

@HaydenYe 我想过，假设右边有两个挨着的同样值的最高点，用你说的旋转只会是这两个点通过的直线，但是我需要的是橘色的线

[inertia]

这条线可以这么定义，在点集中取两个点，将其连成一条直线，点集中的除这两个点外的所有点都在直线之下

[Stoulla]

7 楼应该是正解，这玩意儿就是找一个凸包

[ly90907]

@codehz 就是类似于不平整的地面上放一根直尺，我想测量离尺最远的地面的距离，当然如果地面是突起的，那我觉得应该就是地面中心做切线吧

[ly90907]

@inertia 对对对，我就是这个意思，我语文能力太捉急了

[ynyounuo]

我觉得如果直线是无限长度的，那么落点必然是两个 local maxima，用 scipy 的 find_peaks 找两个最高点，两点求方程就不用说了吧

[Mithril]

你这个本质上是在计算凸包的一条边。先把凸包算出来就好了。

[ryd994]

这个解可能不唯一啊
如果是 1 2 1
那么有两个解
如果是 1 2 2 1
那么可以有三个解

[sujin190]

搞不懂这个的问题难点在哪，楼主既然已经画了二维平面，那么直线下落到最高的必然是所有数据中两个最大值上啊，没有其他情况了吧，两个点确定一个方程组这种小学应用题还用来问啊

[Vinty]

遍历一遍局部峰值点，找全局最高点，然后搜索局部峰值
假设峰值点的集合为 d = {X,Y}, 最高点和其中一条峰值点的直线为 ax+b
所有的 aX+b > =Y 时，就是满足条件的解。搜索方法应该还能再改进，暂时没想到
但是，如果是这样的，会有两个解

[GuuJiang]

首先你得定义整个范围的左右边界，找出其中点 m，然后找到 y 最大的点，如果 m 在其左侧则逆时针旋转，在右侧则顺时针旋转，找到下一个碰到的点，如 m 介于两点的 x 之间，则中止，者两点就是所求，否则 m 必然位于两点同侧，那继续在哪侧就像哪侧旋转，重复直至 m 位于两点之间

[Mithril]

算凸包的时候加上两个点，（ 0,0 ）和（ max_x, 0 ），算出来的凸包去掉那三条固定的边，然后剩下的边里面挑个斜率最接近 0 的就行了。

[whileFalse]

题目有问题，因为无法比较两条 [直线] 的重力势能。如楼上的 1,2,2,1，如何比较 1，2 和 2，2 的重力势能哪个大？