wayetan
2/4/2014 - 8:38 AM

Max Points on a Line

Max Points on a Line

/**
 * Given n points on a 2D plane, find the maximum number of points that lie on the same straight 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) {
    	HashMap<Double, Integer> map = new HashMap<Double, Integer>();
		int res = 0;
		for (int i = 0; i < points.length; i++) {
			Point cur = points[i];
			int add = 1; // duplicates points
			int invalidLine = 0; // vertical line
			for (int j = i + 1; j < points.length; j++) {
				Point tmp = points[j];
				if(tmp.x == cur.x){
					if(tmp.y == cur.y){
						add++;
					}else{
						invalidLine++;
					}
				}else{
    				double slp = slope(cur, tmp);
    				int num = 0;
    				if(map.containsKey(slp)){
    					num = map.get(slp) + 1;
    				}else{
    					num = 1;
    				}
    				map.put(slp, num);
				}
			}
			invalidLine += add;
			res = Math.max(res, invalidLine);
			for(Integer m : map.values()){
				m += add;
				if(res < m)
					res = m;
			}
			map.clear();
		}
		return res;
	}
	private double slope(Point a, Point b){
		if(a.y == b.y)
			return 0.0;
		return 1.0 * (a.y - b.y) / (a.x - b.x);
	}
}