http://oj.leetcode.com/problems/max-points-on-a-line/

Max Points on a Line.cpp

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
bool operator<(const Point &p1, const Point &p2) {
    if (p1.x<p2.x) return true;
    else if (p1.x==p2.x) return p1.y<p2.y;
    else return false;
}
bool operator==(const Point &p1, const Point &p2) {
	return p1.x==p2.x && p1.y==p2.y;
}
class Solution {
public:
	struct Line {
		int a, b, c;
		Line(int _a=0, int _b=0, int _c=0) : a(_a), b(_b), c(_c) {}
		bool operator==(const Line &l) const {
			return a==l.a && b==l.b && c==l.c;
		}
	};
	struct LineHasher {
		size_t operator()(const Line &l) const {
			return 31*31*l.a + 31*l.b + l.c;
		}
	};
	int gcd(int x, int y) const {
		if (x<y) return gcd(y, x);
		if (y==0) return x;
		else return gcd(y, x%y);
	}
	Line solve(const Point &p1, const Point &p2) const { // get the line defined by two different points.
		Line l;
		if (p1.x==p2.x) {
			l.a=1; l.b=0; l.c=-p1.x;
		} else {
			l.b=p1.x-p2.x;
			l.a=(p2.y-p1.y);
			l.c=-(p2.y-p1.y)*p1.x-(p1.x-p2.x)*p1.y;

			int gcd1=gcd(abs(l.a), abs(l.b));
			int gcd2=gcd(abs(l.b), abs(l.c));
			int gcd3=gcd(gcd1, gcd2);
			l.a/=gcd3; l.b/=gcd3; l.c/=gcd3;
			if (l.b<0) {
				l.a*=-1; l.b*=-1; l.c*=-1;
			}
		}
		return l;
	}
	int maxPoints(vector<Point> &points) {
		m_.clear();  int N=points.size();  int max_l=0;
		sort(points.begin(), points.end());
		for (int i=0; i<N;) {
			int same_count=1;
			for (int j=i+1; j<N; ++j) {
				if (points[i]==points[j]) ++same_count;
				else {
					Line l=solve(points[i], points[j]);
					auto it=m_.find(l);
					if (it!=m_.end() && it->second.first==points[i]) {
						it->second.second += 1;
						max_l=max(max_l, it->second.second);
					} else if (it==m_.end()) { 
						m_[l]=make_pair(points[i], same_count+1);
						max_l=max(max_l, same_count+1);
					}
				} 
			}
			max_l=max(max_l, same_count);
			i+=same_count;
		}
		return max_l;
	}
	unordered_map<Line, pair<Point, int>, LineHasher> m_;
};

This problem really has something worthy to note.

Time complexity

http://stackoverflow.com/questions/2734301/given-a-set-of-points-find-if-any-of-the-three-points-are-collinear
According to this article, the problem above is 3-sum hardness, so there are no known solution which is faster than O(N^2).

Implementation

So we just use an hash table and insert C(N, 2) lines into it, than we get the answer, isn't it?
Note that:

1. How do you represent and hash an line? y=kx+b is a bad idea because k will be DBL_MAX or float number, but we have input points in integer representation, it is absolutely not surprising that absolute correctness is required. If double is used, two slightly different lines might be taken as a same one.
   So I use ax+by+c=0. and make sure b>=0 && a, b, c are divided by their gcd.
   When calculating gcd, note that value of a%b is implementation defined when one of the operand is negative.
2. You need to handle the same points. Say we have 3 three same points (0, 0), the result should be 3.
   For [(0, 0), (0, 0), (1, 1), (1, 1)], the result should be 4.