作一条直线，求思路

mahuan1279 · 发表于 2025-7-21 16:01:44

本帖最后由 mahuan1279 于 2025-7-21 17:34 编辑

先求出多段线凸包，然后求均值点（X=Σxi/N,Y=Σyi/N）所在的竖直线与凸包相交的那条边线即所求。

自贡黄明儒 · 发表于 2025-7-22 07:20:14

highflybird 发表于 2025-7-21 14:17
经过发现，此问题可以在O(N*log(N))时间复杂度内求解，下面是求解的lisp代码：

感谢大师，直接给出了答案。

mahuan1279 · 发表于 2025-7-22 16:04:07

highflybird 发表于 2025-7-21 14:29
发一个演示上来，可以看到效率应该没问题。

是不是判断有点问题？检测图中似乎结果不对。

highflybird · 发表于 2025-7-22 21:00:08

本帖最后由 highflybird 于 2025-7-22 21:33 编辑

mahuan1279 发表于 2025-7-22 16:04
是不是判断有点问题？检测图中似乎结果不对。

问了一下楼主可能那个间距20等分的可以不需要。

如果需要20等分的话，下面的程序和你的输出结果是一致的。

mahuan1279 · 发表于 2025-7-22 21:44:37

highflybird 发表于 2025-7-22 21:00
问了一下楼主可能那个间距20等分的可以不需要。

如果需要20等分的话，下面的程序和你的输出结果是一致 ...

还是有问题。

highflybird · 发表于 2025-7-22 21:56:57

mahuan1279 发表于 2025-7-22 21:44
还是有问题。

重新上传了，你再测试一下

mahuan1279 · 发表于 2025-7-22 22:21:38

highflybird 发表于 2025-7-22 21:56
重新上传了，你再测试一下

这下应该是对的了！

mahuan1279 · 发表于 2025-7-23 10:12:47

highflybird 发表于 2025-7-22 21:56
重新上传了，你再测试一下

逐一累加，然后选取最小和值，是吧？

账号		自动登录	找回密码
密码			注册

[其它] 作一条直线，求思路