题解
虽然通过率看起来比较惨剧，但其实这题只是利用简单的哈希思想。首先猜一下复杂度，如果真能做到O(n)的话，肯定要用到某种不知道的计算几何性质，所以个人更偏向于最低复杂度就是O(n^2)。这样的话，我们遍历一遍点集，将每个点作为起始点，算出到其他所有点的斜率；利用哈希表统计与起始点连线斜率相同的点的数量，取其最大值即为与起始点在同一条直线上的最大点数。注意输入中可能存在重复点，需要单独统计一下，更新最大值的时候加进去即可。
这题可以放心地套用哈希表而不用太顾及浮点误差的问题，这是因为对浮点数的哈希本质上是要基于浮点数的位模式而非其数值。但是输入数据中都是整数坐标点，也就限定了所能算得的任何浮点斜率都是有确定并且相对比较简化的真分数表示——也就意味着分数之间相差不会有非常近的情况，其位模式必定完全不同。同时也意味着不同的两个斜率，表示的一定不是同一条直线，而非以相差极小的方式去描述同一条直线。上述讨论，是可以用哈希思想求解本题的理论基础。
代码
class Solution {
public:
inline bool isSamePoint( const Point & a, const Point & b ) {
return a.x == b.x && a.y == b.y;
}
double calcRate( const Point & O, const Point & p ) {
if ( O.x == p.x ) return double(INT_MAX);
return double( O.y - p.y ) / ( O.x - p.x );
}
int maxPoints(vector<Point> &points) {
int ans = 0;
for ( int i = 0; i < points.size(); i++ ) {
unordered_map<double, int> s;
int numSame = 1;
for ( int j = i + 1; j < points.size(); j++ ) {
if ( isSamePoint(points[i], points[j]) ) {
numSame++;
continue;
}
s[calcRate(points[i], points[j])]++;
}
int _max = 0;
for ( auto iter: s ) _max = max(_max, iter.second);
ans = max(ans, _max + numSame);
}
return ans;
}
};