LeetCode: Line Max Points

/**
Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o
+------------->
0  1  2  3  4
Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6
*/
import java.util.*;

class Point{
double x, y;
Point(double x1, double y1){
x = x1;
y = y1;
}
public String toString(){
return "("+x+","+y+")";
}
}

class Line{
public static double epsilon = .8001;
public double slope;
public double intercept;

private boolean infinite_slope = false;

public Line(Point p, Point q) {
if (Math.abs(p.x - q.x) > epsilon) { // if x’s are different
slope = (p.y - q.y) / (p.x - q.x); // compute slope
intercept = p.y - slope * p.x; // y intercept from y=mx+b
} else {
infinite_slope = true;
intercept = p.x; // x-intercept, since slope is infinite
}
}

public boolean isEquivalent(double a, double b) {
return (Math.abs(a - b) < epsilon);
}

public static double floorToNearestEpsilon(double d) {
int r = (int) (d / epsilon);
return ((double) r) * epsilon;
}
 
public boolean isEquivalent(Object o) {
Line l = (Line) o;
    if (isEquivalent(l.slope, slope) && isEquivalent(l.intercept, intercept) && (infinite_slope == l.infinite_slope)) {
    return true;
    }
        return false;
    }   

public String toString(){
return "("+slope+","+intercept+")";
}
}
public class LineMaxPoints{

/**
-use hashmap to store the slope and intercept and keep track of the number of points that satisfy this slope-intercept
-the slopes might differe by very small value and the hashing function may not cover exactly this, so we check three keys slope-epsilon, slope, slope+epsilon in the hashmap for the points
*/
public static int maxPoints(Point[] points) {
Line bestLine = null;
int maxPoints = 0;
HashMap<Double, List<Line>> map = new HashMap<>();
for(int i=0;i<points.length; i++){
Point p1 = points[i];
for(int j=i+1; j<points.length; j++){
Point p2 = points[j];
Line line = new Line(p1, p2);
addLineToMap(map, line);
int count = countSimilarLines(map, line);
if(count>maxPoints){
bestLine = line;
maxPoints = count;
}
}
}
System.out.println("best count is:"+maxPoints+" best line is:"+bestLine);
double key = Line.floorToNearestEpsilon(bestLine.slope);
System.out.println("line points are:");
for(Line l:map.get(key)){
System.out.println(l);
}
return maxPoints;
    }

public static void addLineToMap(HashMap<Double, List<Line>> map, Line line){
double key = Line.floorToNearestEpsilon(line.slope);
map.putIfAbsent(key, new ArrayList<Line>());
map.get(key).add(line);
}

public static int countSimilarLines(HashMap<Double, List<Line>> map, Line line){
double key = Line.floorToNearestEpsilon(line.slope);
int count = countSimilarLinesBySlope(map.get(key), line);
count+= countSimilarLinesBySlope(map.get(key - Line.epsilon), line);
count+= countSimilarLinesBySlope(map.get(key + Line.epsilon), line);
return count;

}

public static int countSimilarLinesBySlope(List<Line> lines, Line line){
if (lines == null) {
return 0;
}
int count = 0;
for (Line parallelLine : lines) {
if (parallelLine.isEquivalent(line)) {
count++;
}
}
return count;
}

public static void main(String[] args){
Point[] points = new Point[7];
points[0] = new Point(1,1);
points[1] = new Point(1.5,1);
points[2] = new Point(2.5,1);
points[3] = new Point(3,1);
points[4] = new Point(4,2);
points[5] = new Point(0,2);
points[6] = new Point(0,3);
int count = maxPoints(points);
System.out.println(count);
}
}