给定2D平面上的n个点，找到位于同一直线上的最大点数(Given n points on a 2D plane, find the maximum number of points that lie on the same straight line)

 以下是我试图实施的解决方案 
 
/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
 public class Solution {
    public int maxPoints(Point[] points) {
    int max=0;
    if(points.length==1)
        return 1;
     for(int i=0;i<points.length;i++){
         for(int j=0;j<points.length;j++){
         if((points[i].x!=points[j].x)||(points[i].y!=points[j].y)){
         int coll=get_collinear(points[i].x,points[i].y,points[j].x,points[j].y,points);
                  if(coll>max)
                    max=coll;
                }
                else{

                    **Case where I am suffering**

                }
           }
        }
  return max;
}
public int get_collinear(int x1,int y1,int x2, int y2,Point[] points)
{
    int c=0;
    for(int i=0;i<points.length;i++){
        int k1=x1-points[i].x;
        int l1=y1-points[i].y;
        int k2=x2-points[i].x;
        int l2=y2-points[i].y;
        if((k1*l2-k2*l1)==0)
            c++;
    }
    return c;
}
}
 
 它运行在O（n ^ 3）。 我基本上做的是运行两个循环比较2d平面中的各个点。 然后取2点我将这2个点发送到get_collinear方法，该方法击中由这两个点形成的线与阵列的所有元素，以检查3个点是否共线。 我知道这是一种蛮力方法。 但是，如果输入是[（0,0），（0,0）]，我的结果将失败。 else循环是我必须添加条件以找出这种情况的地方。 有人可以帮我解决这个问题。 在更好的运行时间是否存在更好的解决方案来解决这个问题。 我什么都想不到。 

Below is the solution I am trying to implement
 
/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
 public class Solution {
    public int maxPoints(Point[] points) {
    int max=0;
    if(points.length==1)
        return 1;
     for(int i=0;i<points.length;i++){
         for(int j=0;j<points.length;j++){
         if((points[i].x!=points[j].x)||(points[i].y!=points[j].y)){
         int coll=get_collinear(points[i].x,points[i].y,points[j].x,points[j].y,points);
                  if(coll>max)
                    max=coll;
                }
                else{

                    **Case where I am suffering**

                }
           }
        }
  return max;
}
public int get_collinear(int x1,int y1,int x2, int y2,Point[] points)
{
    int c=0;
    for(int i=0;i<points.length;i++){
        int k1=x1-points[i].x;
        int l1=y1-points[i].y;
        int k2=x2-points[i].x;
        int l2=y2-points[i].y;
        if((k1*l2-k2*l1)==0)
            c++;
    }
    return c;
}
}
 
It runs at O(n^3). What I am basically doing is running two loops comparing various points in the 2d plane. And then taking 2 points I send these 2 points to the get_collinear method which hits the line formed by these 2 points with all the elements of the array to check if the 3 points are collinear. I know this is a brute force method. However in case where the input is[(0,0),(0,0)] my result fails. The else loop is where I have to add a condition to figure out such cases. Can someone help me with the solution to that. And does there exist a better solution to this problem at better run time. I can't think of any.

原文：https://stackoverflow.com/questions/20779024