# A clean java O(n^2) solution with annotation

• public class Solution {

``````class Line{
//slope is null iff it's vertical
//if line is not vertical, intersect is y-intersection
//if line is vertical, intersect is x-intersection
Double slope; Double intersect;
//some pseudo-pseudo random number
static final int rand=65536123;

//clean constructor interface
Line (double slope,double intersect){
this.slope=slope;
this.intersect=intersect;
}

//precondition: alpha and beta not same point
Line (Point alpha,Point beta){
if (alpha.x==beta.x){
this.slope=null;
this.intersect=(double)alpha.x;
}
else {
this.slope=(double)((alpha.y-beta.y)/((double)(alpha.x-beta.x)));
this.intersect=(beta.y*alpha.x-alpha.y*beta.x)/((double)alpha.x-beta.x);
}
}

@Override
public boolean equals(Object beta){
boolean output=false;
if (beta instanceof Line){
Line betaLine=(Line) beta;
return ((this.slope==null && betaLine.slope==null)||approxEqual(this.slope,betaLine.slope))&&approxEqual(this.intersect,betaLine.intersect);
}
return output;
}

@Override
public int hashCode(){
final int prime = 31;
int result = 1;
result = prime * result + (this.slope==null?rand:this.slope.hashCode());
result = prime * result + (this.intersect==null?rand:this.intersect.hashCode());
return result;
}

public String toString(){
String output="";
output+="slope: "+(this.slope==null?"null":this.slope)+"intersect: "+(this.intersect==null?"null":this.intersect);
return output;
}
}

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

//O(n^2) algo
public int maxPoints(Point[] points) {
//case defense: there is always a line when only one point
if (points==null || points.length==0) return 0;
if (points.length==1) return 1;
//key: Line; Value: the count of points in this line
HashMap<Line,HashSet<Point>> H=new HashMap<Line,HashSet<Point>>();

for (int i=1;i<points.length;i++){
Point iPoint=points[i];
for (int j=0;j<i;j++){
Point jPoint=points[j];
Line Line_IJ=new Line(iPoint,jPoint);
//if two same points, let the line be null
if (approxEqual(iPoint.x,jPoint.x)&& approxEqual(iPoint.y,jPoint.y))  Line_IJ=null;

//if H does not contain Line_IJ, just put (Line_IJ) into H, add iPoint & jPoint into Line_IJ's pointSet
if (Line_IJ!=null && (!H.keySet().contains(Line_IJ))){
HashSet<Point> pointSet=new HashSet<Point>();
H.put(Line_IJ, pointSet);
}
//if H does contain Line_IJ, corresponding pointSet of Line_IJ
//if pointSet does not iPoint/jPoint, add iPoint/jPoint to pointSet,
else if (Line_IJ!=null){
HashSet<Point> pointSet=H.get(Line_IJ);
}

}
}
//now we have all the lines, we want to fit points on the lines

//another defense
if (H.size()==0){
HashSet<Point> pointSet=new HashSet<Point>();
H.put(new Line(points[0],points[1]),pointSet);
}

//sweep on the lines on all the points to see if it fits, if fit, add to corresponding HashSet
for (Point p:points){
for (Line L:H.keySet()){
//L is vertical?
if (L.slope==null){
}
else {
}
}
}

int output=0;
for (Line L:H.keySet()){
if (H.get(L).size()>output) output=H.get(L).size();
}
return output;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.