Leetcode: Max Points on a Line

Use HashMap to keep track of all distinct lines.  In worst case,  there can be n*(n-1) distinct lines.

The implementation of class Line is crucial. It has to full fill the following requirements:

1. override equals() and hashCode(), so that we can utilize HashMap.
2. deal with the cases where the two points are:

• The same
• Vertical lines
• Parallel lines

Further more, the equals() method, which decide weather two lines are equal or not, need to be very accurate.  Based on this consideration, instead of represent a line using slope and intercept, I choose to represent a line directly by two points, because when accuracy will be degrade when calculating slope and intercepts.  Now since Line is represented by two points, how do we decide whether two Lines are the same or not? Slope and intercepts is not a choice due to accuracy issue. Instead, I use "parallel vector" knowledge:

• If  vector (x1, y1) is parallel to vector (x2, y2), then x1*y2 == x2*y1.

Consider the two points of each line as a vector, we can implement this easily.

public class Solution {
 	public int maxPoints(Point[] points) {
		if (points.length <= 2)
			return points.length;

		HashMap> lines = new HashMap>();

		for (int i = 0; i < points.length - 1; i++) {
			for (int j = i + 1; j < points.length; j++) {
				Line line = new Line(points[i], points[j]);
				if ((points[i].x == points[j].x && points[i].y == points[j].y)) {
					boolean inSet = false;
					for (Line l : lines.keySet()) {
						if (l.onSameLine(points[j])) {
							Set set = lines.get(l);
							set.add(points[i]);
							set.add(points[j]);
							lines.put(l, set);
							inSet = true;
						}
					}
					if (!inSet) {
						Set set = new HashSet();
						set.add(points[i]);
						set.add(points[j]);
						lines.put(line, set);
					}

				}

				else if (!lines.containsKey(line)) {
					Set set = new HashSet();
					set.add(points[i]);
					set.add(points[j]);
					lines.put(line, set);
				} else {

					Set set = lines.get(line);
					set.add(points[i]);
					set.add(points[j]);
					lines.put(line, set);

				}
			}
		}

		int max = 1;
		for (Set set : lines.values()) {
			max = Math.max(max, set.size());
		}
		return max;
	}

	class Line {
		Point A;
		Point B;

		@Override
		public boolean equals(Object line) {
			if (!(line instanceof Line))
				return false;
			else {

				Point C = ((Line) line).A;
				Point D = ((Line) line).B;
				if (A.x == B.x && A.y == B.y && C.x == D.x && C.y == D.y)
					return true;
				boolean parallel = ((A.x - B.x) * (C.y - D.y) == (A.y - B.y)
						* (C.x - D.x));
				boolean sameLineC = onSameLine(C);
				boolean sameLineD = onSameLine(D);

				return parallel && sameLineC && sameLineD;
			}

		}

		public boolean onSameLine(Point C) {
			if ((A.x - C.x) * (B.y - C.y) == (B.x - C.x) * (A.y - C.y))
				return true;
			return false;
		}

		@Override
		public int hashCode() {
			double slope = 0, constant = 0;
			if (A.x == B.x && A.y != B.y)
				slope = Double.POSITIVE_INFINITY;
			else if (A.x == B.x && A.y == B.y) {
				slope = A.x;
				constant = A.y;
			} else {
				slope = (A.y - B.y) / (A.x - B.x);
				constant = A.y - slope * A.x;
			}

			int hash = 3;
			hash = 7 * hash + Double.valueOf(slope).hashCode();
			hash = 7 * hash + Double.valueOf(constant).hashCode();
			return hash;
		}

		Line(Point a, Point b) {
			A = a;
			B = b;
		}
	}
		
	
}