题解 | #多少个点位于同一直线#

题目描述:对于给定的n个位于同一二维平面上的点，求最多能有多少个点位于同一直线上

示例1
        输入：[(0,0),(0,1)]
        返回值：2
示例2
        输入：[(2,3),(3,3),(-5,3)]
        返回值：3
思路：简单直接暴力求解，通过双指针i和j来遍历数组中的每两个点，然后判断其余点是否在这两点组成的直线上来统计点数count和max比较，最后返回max即可，整体而言，算法执行的时间复杂度为O(n),具体代码如下：

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param points Point类vector 
     * @return int整型
     */
    int Compute(vector<Point> points,int i,int j)
    {
        int m=0,count=0,flag = 0;
        if(points[j].y == points[i].y)//水平直线
            flag=1;
        if(points[j].x == points[i].x)//竖直直线
            flag=2;
        if(flag == 0)
        {
             for(;m<points.si***t left = (points[j].x - points[i].x)*( points[m].y - points[i].y);
                 int right = (points[m].x - points[i].x)*( points[j].y - points[i].y);
                 if(left == right)
                     count++;
             }
        }
        else if(flag ==1)
        {
             for(;m<points.size();m++)
             {
                 if(points[m].y == points[i].y)
                     count++;
             }
        }
        else if(flag == 2)
        {
            for(;m<points.size();m++)
             {
                 if(points[m].x == points[i].x)
                     count++;
             }
        }
        return count;
    }
    int maxPoints(vector<Point>& points) {
        // write code here
        //思路，二维平面上一条直线可由两个不同点唯一确定平面方程 （x2-x1)*(y-y1) = (x-x1)*(y2-y1)
        int n = points.size();
        if(n == 0) return 0;
        else if(n == 1) return 1;
        else if(n==2) return 2;
        else
        {
            int max = 2,i=0,j=i;
            while(i<n-1)
            {
                j++;
                int res = Compute(points,i,j);
                if(res > max)
                    max = res;
                if(j == n-1)
                {
                    i++;
                    j=i;
                }
            }
            return max;
        }
    }
};