#yyds干货盘点# LeetCode程序员面试金典：最佳直线

题目：

给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。

设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。

示例：

输入： [[0,0],[1,1],[1,0],[2,0]]

输出： [0,2]

解释： 所求直线穿过的3个点的编号为[0,2,3]

代码实现：

class Solution {
    public int[] bestLine(int[][] points) {
        int numOfPoints = points.length;
        int []res= new int[]{0,1};
        int max_NumOfPoint = 2;    
        //外循环确定点
        for(int i = 0;i<numOfPoints - 1;i++){
            int x1 = points[i][0];
            int y1 = points[i][1];

            //内循环确定一条直线
            for(int j = i + 1;j<numOfPoints;j++){
                int x2 = points[j][0];
                int y2 = points[j][1];
                int line_Points = 2;
                //内内循环确定在线上点的个数
                for(int k = j + 1;k < numOfPoints;k++){
                    int x3 = points[k][0];
                    int y3 = points[k][1];
                    if((y1-y2)*(x1-x3) == (y1-y3)*(x1-x2)){
                        line_Points++;
                    }
                    if(line_Points > max_NumOfPoint){
                        res[0] = i;
                        res[1] = j;
                        max_NumOfPoint = line_Points;
                    }
                }
            }
        }
        return res;
    }
}