Given an array of 2D coordinates of points (all the coordinates are integers), find the largest number of points that can be crossed by a single line in 2D space.

Assumptions

• The given array is not null and it has at least 2 points

Examples

• <0, 0>, <1, 1>, <2, 3>, <3, 3>, the maximum number of points on a line is 3(<0, 0>, <1, 1>, <3, 3> are on the same line)

Solution: 斜率和点确定一条直线。分别统计相同点，水平，垂直，斜率

3种特殊情况：

if(points[j].x == points[i].x && points[j].y == points[i].y){

same++;

continue;

}

if(points[j].x == points[i].x){

//或者斜率以Integer.MAX_VALUE表示

vertical++;

continue;

}

if(points[j].y == points[i].y){

//或者：斜率计算要用0.0＋slop。原因：slop可能结果为-0.0，用0.0＋－0.0=0.0，来防止发生0.0 != -0.0的情况。

horizontal++;

continue;

}

  public int most(Point[] points) {
    if (points.length < 3) {
      return points.length;
    }
    Map<Double, Integer> hashmap = new HashMap<>();
    int max = 2;
    for (int i = 0; i < points.length - 2; i++) {
      if (i > 0 && points[i].x == points[i - 1].x && points[i].y == points[i - 1].y) {
        continue;
      }
      int same = 0, vertical = 1, horizontal = 1, slope = 0;
      for (int j = i + 1; j < points.length; j++) {
        if (points[i].x == points[j].x && points[i].y == points[j].y) {
          same++;
        } else if (points[i].x == points[j].x) {
          vertical++;
        } else if (points[i].y == points[j].y) {
          horizontal++;
        } else {
          double tan = ((double)(points[i].y - points[j].y)) / (points[i].x - points[j].x);
          hashmap.put(tan, hashmap.containsKey(tan) ? hashmap.get(tan) + 1 : 2);
          slope = Math.max(hashmap.get(tan), slope);
        }
      }
      //注意留在最后统计
      max = Math.max(Math.max(Math.max(vertical, horizontal), slope) + same, max);
      hashmap.clear();
    }
    return max;
  }