窮舉--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.

class Solution {

public:

    int maxPoints(vector<Point> &points) {

        //統計在平面上，在同一條直線，包含最多點的數目

        int size = points.size();

        if(0 == size)

            return 0;

        else if(1 == size)

            return 1;

        int ret = 0;

        for(int i = 0; i < size; i++)

        {

            map<double, int> kmp;

            int dup = 0;

            int vcnt = 1;

            int curmax = 1;

            for(int j = i + 1; j < size; j++)

            {

                double x1 = points[i].x - points[j].x;

                double y1 = points[i].y - points[j].y;

                if(0 == x1 && 0 == y1)//重疊點

                    dup++;

                else if(0 == x1 && 0 != y1)//垂直

                {

                    vcnt++;

                    curmax = max(vcnt, curmax);

                }

                else

                {

                    double k = y1 / x1;

                    if(0 == kmp[k])

                        kmp[k] = 2;

                    else

                        kmp[k]++;

                    curmax = max(kmp[k], curmax);

                }

            }

            ret = max(ret, curmax + dup);

        }

        return ret;

    }

};