寄托家园留学论坛

标题: 准备面试问这个题目各位看看 [打印本页]

作者: nynyaaa 时间: 2011-4-21 01:24:04 标题: 准备面试问这个题目各位看看

职位：Java Dev

输入，List<Point>

Point是一个平面坐标系上的点

求该list中的3点，以其为顶点构成的三角形面积最大。

该list很大，要求一个高效的算法。

写一个程序。Point要自己实现。

作者: DriverEntry 时间: 2011-4-21 09:18:17

没想到啥好算法。。。挫人飘过。。。

作者: nynyaaa 时间: 2011-4-21 10:24:24

直接想到的是先求凸包，非凸包上的点删掉，然后。。。。先枚举着
soonyu 发表于 2011-4-21 09:27

凸包O(nlogn)，凸包后，如果在做凸包时就把点排号，可以O(n)

作者: nynyaaa 时间: 2011-4-21 10:25:21

因为我可以把所有点都放在凸包上，这样你枚举的最坏情况就是O(n^3)了

欢迎光临寄托家园留学论坛 (https://bbs.gter.net/)