算法练习(79): 三点共线(1.4.26)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 三点共线

题目

1.4.26 三点共线。假设有一个算法，接受平面上的 N 个点并能够返回在同一直线上的三个点的组数。证明你能够用这个算法解决 3-sum 问题。

1.4.26 3-collinearity. Suppose that you have an algorithm that takes as input N dis- tinct points in the plane and can return the number of triples that fall on the same line. Show that you can use this algorithm to solve the 3-sum problem. Strong hint: Use algebra to show that (a, a3), (b, b3), and (c, c3) are collinear if and only if a + b + c = 0.

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。