# Java Accepted Solution o(n^2)

• The idea is to use slope and intercept to specify a line. Instead of using double, which could have precision problem, I use int array to specify params for a line. GCD is used to make numerator and denominator to be co-prime. Two corner cases need to be considered: vertical and horizontal line.

/**
* Definition for a point.
* class Point {
*     int x;
*     int y;
*     Point() { x = 0; y = 0; }
*     Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
public int maxPoints(Point[] points) {
if (points.length == 1) return 1;
HashMap<Line, HashSet<Integer>> hash = new HashMap<Line, HashSet<Integer>>();
for (int i = 0; i < points.length; i++) {
for (int j = i+1; j < points.length; j++) {
Line slope = computeSlope(points[i], points[j]);
if (!hash.containsKey(slope)) hash.put(slope, new HashSet<Integer>());
// System.out.println(slope);
}
}
int max = 0;
for (HashSet<Integer> set: hash.values()) {
max = Math.max(max, set.size());
}
return max;
}
// y-y1 = k*(x-x1)
// y = (y2-y1)/(x2-x1)*x +(y1*(x2-x1)- x1*(y2-y1))/(x2-x1)
private Line computeSlope(Point a, Point b) {
int[] result = new int[4];

if (b.x-a.x == 0) {
result[0] = Integer.MAX_VALUE;
result[1] = 0;
result[2] = a.x;
result[3] = 0;
} else if (b.y-a.y == 0) {
result[0] = 0;
result[1] = 0;
result[2] = 0;
result[3] = a.y;
} else {
int n = b.y-a.y;
int d = b.x-a.x;
int g = gcd(Math.abs(n), Math.abs(d));
if ((n > 0 && d > 0)||(n < 0 && d < 0)) {
result[0] = Math.abs(n)/g;
result[1] = Math.abs(d)/g;
} else {
result[0] = -Math.abs(n)/g;
result[1] = Math.abs(d)/g;
}

n = a.y*(b.x-a.x)-a.x*(b.y-a.y);
d = b.x-a.x;
g = gcd(Math.abs(n), Math.abs(d));
if ((n > 0 && d > 0)||(n < 0 && d < 0)) {
result[2] = Math.abs(n)/g;
result[3] = Math.abs(d)/g;
} else {
result[2] = -Math.abs(n)/g;
result[3] = Math.abs(d)/g;
}
}

return new Line(result);
}

class Line{
public int[] params = null;
public Line(int[] params) {
this.params = params;
}

public int hashCode() {
long res = 0;
for (int n: params) {
res = res*37+n;
}
return (int)res;
}

public boolean equals(Object a){
if (a == null) return false;
for (int i = 0; i < this.params.length; i++) {
if (this.params[i] != ((Line)a).params[i]) return false;
}
return true;
}
}

private int gcd (int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
}

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