# 2 Java Solutions, similar algorithm, different implementation

• Solution 1:

``````        public int maxPoints(Point[] points) {
int max = 0;
if (points == null || points.length == 0) return 0;
int n = points.length;
if (n == 1) return 1;
for (int i = 0; i < n - 1; ++i) {
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
int dup = 0, lclmax = 0;
for (int j = i + 1; j < n; ++j) {
int x = points[j].x - points[i].x;
int y = points[j].y - points[i].y;
if (x == 0 && y == 0) {
++dup;
continue;
}
int gcd = gcd(x, y);
x /= gcd;
y /= gcd;
if (!map.containsKey(x)) map.put(x, new HashMap<Integer, Integer>());
if (!map.get(x).containsKey(y)) map.get(x).put(y, 0);
map.get(x).put(y, map.get(x).get(y) + 1);
lclmax = Math.max(lclmax, map.get(x).get(y));
}
max = Math.max(max, dup + lclmax + 1);
}
return max;
}

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

Solution 2:

``````        private class Frac {
int dvd, dvs;
public Frac (int a, int b) {
int gcd = gcd(a, b);
dvd = a / gcd;
dvs = b / gcd;
}
private int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
@Override
public int hashCode() {
return dvd * 100007 + dvs * 1007 + 17;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Frac)) return false;
Frac other = (Frac) o;
return dvd == other.dvd && dvs == other.dvs;
}
}
private class Line{
Frac a, b;
public Line(Point p1, Point p2) {
if (p1.x == p2.x) {
a = null;
b = new Frac(p1.x, 1);
} else {
a = new Frac(p1.y - p2.y, p1.x - p2.x);
b = new Frac(p1.x * p2.y - p2.x * p1.y, p1.x - p2.x);
}
}
@Override
public int hashCode() {
return (a == null ? 0 : a.hashCode() * 100013) + b.hashCode() * 10013 + 13;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Line)) return false;
Line other  = (Line) o;
return (a == null && other.a == null || a.equals(other.a)) && b.equals(other.b);
}
}
public int maxPoints(Point[] points) {
if (points == null || points.length == 0) return 0;
int n = points.length;
if (n == 1) return 1;
Map<Line, Set<Point>> map = new HashMap<>();
int max = 0;
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
Line line = new Line(points[i], points[j]);
if (!map.containsKey(line)) {
map.put(line, new HashSet<Point>());
}