Max Points on a Line.3.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) {}
 * };
 */
struct cmp{
    bool operator()(const Point&a,const Point&b){
        return a.x<b.x || (a.x==b.x && a.y<b.y);
    }
};
class Solution {
public:
    bool on_a_line(const Point&a,const Point&b,const Point&c){
        return (a.x-b.x)*(a.y-c.y) == (a.y-b.y)*(a.x-c.x);
    }
    int maxPoints(vector<Point> &points) {
        if(points.size()<=2)return points.size();
        int ret=0;
        map<Point,int,cmp>hash;
        for(int i=0;i<points.size();i++)
            hash[points[i]]++;
        if(hash.size()==1)return hash.begin()->second;
        for(map<Point,int>::iterator iti=hash.begin();iti!=hash.end();iti++)
            for(map<Point,int>::iterator itj=next(iti);itj!=hash.end();itj++){
                int r=iti->second+itj->second;
                for(map<Point,int>::iterator itk=next(itj);itk!=hash.end();itk++)
                    if(on_a_line(iti->first,itj->first,itk->first))
                        r+=itk->second;
                ret=max(ret,r);
            }
        return ret;
    }
};