※ [本文转录自 CSSE 看板 #1GnqICKG ]
作者: wangtrying (老王) 看板: CSSE
标题: [问题] 面试问到的问题...
时间: Tue Dec 11 22:34:50 2012
在 XY 平面上,
给n个点 Pi = (Xi, Yi), i = 1...n,
找出最多点共线时 这条线上面的点的个数
怎么解的漂亮啊?
小弟想得到的就是暴力法
每两个点算斜率 m
放到一个Dictionary的资料结构
key是m, value是出现次数...
所以 总共会计算 n(n-1)/2 次 m 值
然后再对Dictionary的value找最大值 就是解了
但是这样是O(n^2) 不知道大家有没有更好的做法?

这样做是 O(n^3) 喔, 计算出现次数要 n

big O的话, n会被n^2盖掉吧? 还是我有误会你的意思?

找出最多点共线时线上的点数 所以位置不同 斜率相同的线是不同的所以粗估每个斜率有 n 种可能(n个点) 当然可能少于这数字

ㄟ 不好意思 我可能没有把题目叙述得很好...orz我印象中他的意思应该是说 比如说 洒两个点在平面上那得到的值当然是2, 洒三个点, 而这三个点形成三角形那也是2, 但是说这三个点刚好共线的话, 那就是3了然后现在撒了n个点在平面上, 假如恰好有四点共线那就是4, 大概是这样啦...

可以考虑这样：现在 x=0 的线上有 10 个点x=1 的线上有 11 个点x=2 的线上有 13 个点那计算共线时 x=0, x=1, x=2 这三条铅直线不会只算一次或者说 斜率一样不代表他们贡献共线

阿 我懂了 感谢suhorng大大 Y=mX+b, m跟b都要算出来

最快的做法应该是依序固定一个点，计算其他所有点跟该点的斜率，然后用hash加速统计，O(n^2)

斜率是不够的, 以suhorng大大的例子来说, 正确答案是13但是只算斜率的话 会得到34 就错了所以应该要用<m,b>的tuple当key, 丢到hash里面

hash是对的 就是枚举点然后转一圈然后相对于这个点斜率相同的就是在同条线上

姆…我的意思是针对每个点分别计算跟其他点的斜率

感谢wtvwtvwtv200跟suhorng两位大大 orz

看到推文了XD 差不多例子

wtv大 的意思是说 每转一圈就纪录斜率出现次数的最大值这样好像比较漂亮喔

＂转一圈＂这个形容不太对，因为要排序的话复杂度会变成O(n^2logn)，用hash不管顺序直接扫O(n2)