# AUG!!! 28ms JAVA Solution! Use your Object Oriented thoughts! O(n2) Commented.

• ``````public class Solution {
class Line{
double epsilon = 0.0001;//difference within this range is considered to be the same. You could delete it or change this number to any one as long as it can work.
double yIntercept;//Basic idea that you must agree is that a slope and y-intercept can determine a line
double slope;
boolean infiniteSlope = false;//for lines which are perpendicular to x-axis, this is true;
Line(Point p1, Point p2){
if(p1.x == p2.x){
this.yIntercept = p1.x;
infiniteSlope = true;
}else{
//Compute the slope and y-intercept when the line is not perpendicular to x-axis
slope = (double)(p1.y - p2.y)/(p1.x - p2.x);
yIntercept = (double)p1.y - slope*p1.x;
}
}
// The following is the key for this code.
// We need to overwrite hashCode() and equals() function here. We are going to save Line as the key and points on the Line as values into hashmap.
//When we are searching whether a Line exists in the hashMap, containsKey method will call hashCode() function to find if the hashCode of the key we are searching matches any
// keys' hashCode in the map.If there is a match, then it will continue to call equals method to judge whether they are really equal. If yes, return true, if not, return false;

//Overwrite hashCode function
public int hashCode(){
// Here, you can use any calculation to return values which can distinguish different line, and return the same value when two line are the same.
long yTemp =  (long)(yIntercept * 10000);//I chose 10000, because I chose .0001 as tolerance
long slopeTemp = (long) (this.infiniteSlope?0:this.slope*10000);
return (int)(yTemp/123+slopeTemp/313);//123 and 313 can be replaced
}
// One thing you really need to pay attention here is that parameter here must be Object, and then you can change it into Line.
public boolean equals(Object obj){
Line l = (Line) obj;
if(this.infiniteSlope){
return l.infiniteSlope ? (Math.abs(this.yIntercept - l.yIntercept) < epsilon):false;
}
if(!l.infiniteSlope){
return Math.abs(this.yIntercept - l.yIntercept) < epsilon && Math.abs(this.slope - l.slope) < epsilon;
}
return false;
}
/*public void print(){
System.out.println((infiniteSlope?"This one has a infiniteSlope":("The slope is " + this.slope)) + " the yIntercept is "+ yIntercept+" and hasCode is " +this.hashCode());
}*/

}
public int maxPoints(Point[] points) {
if(points == null || points.length == 0)
return 0;
if(points.length < 3)
return points.length;
int maxPointsOnLine = 2;
Line currentLine;
HashSet pointsSet;
HashMap<Line, HashSet<Point>> map = new HashMap<>();
//Do not use arraylist here because you do not want to include duplicate points for the same line.
for(int i = 0; i < points.length; i++){
for(int j = i+1; j < points.length; j++){
currentLine = new Line(points[i], points[j]);
if(!map.containsKey(currentLine)){
HashSet<Point> currentSet = new HashSet<>();
map.put(currentLine,currentSet);
}else{
pointsSet = map.get(currentLine);