public int maxPoints(Point[] points) { if(points == null || points.length == 0) return 0; HashMap<Double, Integer> result = new HashMap<Double, Integer>(); int max=0; for(int i=0; i<points.length; i++){ int duplicate = 1;// int vertical = 0; for(int j=i+1; j < points.length; j++){ //handle duplicates and vertical if(points[i].x == points[j].x){ if(points[i].y == points[j].y){ duplicate++; }else{ vertical++; } }else{ double slope = points[j].y == points[i].y ? 0.0 : (1.0 * (points[j].y - points[i].y)) / (points[j].x - points[i].x); if(result.get(slope) != null){ result.put(slope, result.get(slope) + 1); }else{ result.put(slope, 1); } } } for(Integer count: result.values()){ if(count+duplicate > max){ max = count+duplicate; } } max = Math.max(vertical + duplicate, max); result.clear(); } return max; }
Tuesday, January 31, 2017
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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment