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

[ly90907]

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

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

[lidlesseye11]

感觉楼主想要的是个类似于豪斯多夫距离的概念？
满足 9L 描述的有不止一条直线，定义 Di 为点 i 到直线的距离的话，楼主想要的是使 max （ Di ）最小的那条线？

[shyrock]

1.下落到最高点，如果最高点多于 2 个，则解是连接这两个点的直线。
2.如果最高点只有一个，则判断最高点在左侧还是右侧，然后以最高点为原点，对侧的点按极坐标排序，第一个扫到的点和最高点确定直线

[lidlesseye11]

@lidlesseye11 又或者是使 sum （ Di ）最小的那条线？

[akira]

找到最高点
以最高点为原点建立极坐标
扫描两侧的点
所以应该是有 2 个解...

[rus4db]

关键词：凸包算法

[wa007]

找到最高点，最高点肯定经过这条直线，然后遍及其他点，与最高点连成一条直线，斜率绝对值最小的直线就是答案

[LxExExl]

楼主如果是炒股我觉得技术分析啥的都没用

各种均线看看就行了 还是选成长股优质股然后长线定投

[oylinv]

这个的话，最简单的方法，就是按顺序取两个点，用这两条点建立直线，再判断其他点是否在这条线下方（点到直线距离公式去掉绝对值）， 如果存在上方的点，则顺序换接下来的两个点计算。
就是计算次数比较多

[ly90907]

感谢各位的回复和解答，由于人数较多就不一一回复了，看了各位的回答，并且思考 @GuuJiang 和 @Jirajine 这两位朋友的回复就是我想要的答案。并且整理了一下，写了一个总结。https://zhuanlan.zhihu.com/p/367706616
懒得点的话我就直接把伪代码贴上，以供分享。


遍历点集找出最高点 P1 ；

if P1∈[0，N ） 遍历 P1 右边的点，计算斜率 k，找出 k 最大的点 P2 ；

if P2∈[N，2N ） 得到 P1，P2 为最终结果

else P1 = P2， 递归上述过程

else if P1∈[N，2N ） 遍历 P1 左边的点，计算斜率 k，找出 k 最小的点 P2 ；

if P2∈[0，N ） 得到 P1，P2 为最终结果

else P1 = P2， 递归上述过程



@sujin190
@ryd994
@Vinty
@whileFalse
@zxCoder
@stonewolfcjq
@aneureka
@ho121
@3dwelcome
@oamu
@shyrock
@wa007
@LxExExl
@oylinv

[ryd994]

既然反正是 O(n^2)
那直接遍历经过每每两点的直线，使得直线在 1/2 处的值最大化即可
这样做虽然计算量大一点，但是可以很容易并行化

[ly90907]

@ryd994 我在八楼回复的图，绿线在 1/2 处比黄线的要大，但是黄线才是要得到的。不知道我的理解对不对