如何查找位於同一條直線上的最大點數

Question

假設您在2D平面上有點陣列。點定義如下：

class Point { 
    public int x; 
    public int y; 

    Point(int _x, int _y) { x = _x; y = _y; } 
} 

我怎麼能找到在java中同一直線上的最大點數？

Answer 1

/** 
* Definition for a point. 
* struct Point { 
*  int x; 
*  int y; 
*  Point() : x(0), y(0) {} 
*  Point(int a, int b) : x(a), y(b) {} 
* }; 
*/ 
class Solution { 
public: 
    int maxPoints(vector<Point> &points) { 
     int n = points.size(); //number of the points 
     if (n<=2){return n;} 
     vector<double> k; //vector to store the slops for one point with all the other points 
     int res = 0; 

     for (int i=0;i<n;i++){ // for each point in the 2d plane 
      k.clear(); 
      int dup = 1; // number of the duplicates with currrent point 
      for (int j=0;j<n;j++){ 
       if (i!=j){ // for every other point 
        if (points[i].x-points[j].x==0){ // if the slope is a vertical line 
         if (points[i].y-points[j].y==0){ // if the point j is the same as point i 
          dup++; 
         }else{ 
          k.push_back(99999); //store the vertical line to a specific slope 
         } 
        }else{ // if it is the regular slop between point i and j 
         k.push_back(10000*(points[i].y-points[j].y)/(points[i].x-points[j].x)); // store the slope 
        } 
       } 
      } 

      sort(k.begin(),k.end()); //sort the slopes for counting 

      int pp = 1; //number of points in the same line of the point i 
      if (k.size()==0){pp=0;} 

      for (int jj=1;jj<k.size();jj++){ //count pp 
       if (k[jj]==k[jj-1]){ 
        pp++; 
       }else{ 
        if (pp+dup>res){res=pp+dup;} // res = pp + the number of duplicates 
        pp = 1; 
       } 
      } 
      if (pp+dup>res){res = pp+dup;} 
     } 

     return res; 
    } 
}; 

Answer 2

對於數組中的每個點，計算此點與其他點之間的角度。使用hashMap計算具有相同角度的人數。預計時間爲O（n^2）

僞代碼

int result = 0; 
for(int i = 0; i < data.length; i++){ 
    HashMap<Double, Integer> map = new HashMap(); 
    for(int j = 0; j < data.length; j++){ 
     if(i == j) 
      continue; 
     double angle = calculateAngle(data[i], data[j]); 
     if(map.containsKey(slope)){ 
      map.put(angle, map.get(slope) + 1); 
     }else{ 
      map.put(angle, 1); 
     } 
     result = max(result, map.get(slope)); 
    } 
} 

注：如NiklasB的評論提到，採用雙會導致一些問題的精度，尤其是當我們需要比較這些浮點值。我們可以通過使用NiklasB建議的Rational類來避免這種情況。 （或者不那麼精確，使用this）

Answer 3

下面是使用精確的算法在Java中的解決方案：

import java.util.List; 
import java.util.Map; 
import java.util.HashMap; 

public class Solver { 
    public int maxPointsOnLine(List<Point> points) { 
     int ans = 0; 
     Map<Line, Integer> lines = new HashMap<Line, Integer>(); 
     for (Point a : points) { 
      int max = 0; 
      int same = 0; 
      lines.clear(); 

      for (Point b : points) { 
       if (a.x == b.x && a.y == b.y) { 
        ++same; 
       } else { 
        Line line = new Line(b.x - a.x, b.y - a.y); 
        Integer count = lines.get(line); 
        if (count == null) { 
         count = 0; 
        } 
        ++count; 
        lines.put(line, count); 
        max = Math.max(max, count); 
       } 
      } 
      ans = Math.max(ans, same + max); 
     } 
     return ans; 
    } 

    static class Line { 
     final int dx; 
     final int dy; 

     Line(int dx, int dy) { 
      if (dy == 0) { 
       dx = Math.abs(dx); 
      } 
      else if (dy < 0) { 
       dx = -dx; 
       dy = -dy; 
      } 
      int gcd = gcd(Math.abs(dx), dy); 
      dx /= gcd; 
      dy /= gcd; 
      this.dx = dx; 
      this.dy = dy; 
     } 

     @Override 
     public boolean equals(Object other) { 
      if (!(other instanceof Line)) { 
       return false; 
      } 
      Line another = (Line)other; 
      return dx == another.dy && dy == another.dy; 
     } 

     @Override 
     public int hashCode() { 
      return 31 * dx + dy; 
     } 
    } 

    static int gcd(int a, int b) { 
     return b == 0 ? a : gcd(b, a % b); 
    } 
}