Leetcode中平面几何相关的题目

1. Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
用斜率slope和y截距来定义一条直线是通常的做法，那么n个线段里两两配对，然后把slope和截距记录到hashtable里。这样的算法比较复杂。另一种简单的做法是依次选取一个点 P， 然后考察其他点和他的斜率，如果线段AP和BP的斜率一样，那么ABP三个点是共线的，这样就省去了截距的计算。 当然每一次iteration hashtable要清空，因为AP 和BQ的斜率即便一样，也未必是同一条线。最后要注意重复点的问题。