学步园

Given n points
on a 2D plane, find the maximum number of points that lie on the same straight line.

思路：暴力方法。先确定线段的一个点a，然后遍历剩下的点b1,b2,...bn-1，由于起始点确定，剩下的b1,b2...bn-1如果与a确定的斜率相等，则共线。对于b1,...bn-1有两处需要注意：1.斜率不存在。2.与a为同一个点。考虑这两种情况思路就清晰了。

class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int len = points.size();
        if (len <= 1) {
            return len;
        }
        int i,j,max=INT_MIN,per;
        map<double,int> slope;
        double k;
        int same;
        for(i=0; i<len; ++i) {
            slope.clear();
            same = 1;
            per = 0;
            for(j=i+1; j<len; ++j) {
                if((points[i].x == points[j].x)&&(points[i].y!=points[j].x)) {
                    k = INT_MAX;
                }
                if(points[i].x==points[j].x&&points[i].y==points[j].y) {
                    same++;
                    continue;
                }    
                if(points[i].x != points[j].x) {
                    k = (points[j].y-points[i].y)*1.0/(points[j].x-points[i].x);
                }
                if (slope.find(k) != slope.end()) {
                    slope[k]++;
                }
                else {
                    slope.insert(pair<double,int>(k,1));
                }
                per = (per<slope[k] ? slope[k] : per);
            }
            max = (max<per+same?per+same:max);
        }
        return max;
    }
};