Max Points on a Line
LintCode-186.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.
Example
Given 4 points: (1,2), (3,6), (0,0), (1,3).
The maximum number is 3.
/**
* 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 {
/**
* @param points an array of point
* @return an integer
*/
public int maxPoints(Point[] points) {
if (points == null || points.length == 0) {
return 0;
}
int max = 1;
HashMap<Double, Integer> map = new HashMap<Double, Integer>();
for (int i = 0; i < points.length - 1; i++) {
int duplicate = 0;
int localmax = 1;
double slope = 0.0;
for (int j = i + 1; j < points.length; j++) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
duplicate++;
continue;
} else if (points[i].x == points[j].x) {
slope = Integer.MAX_VALUE;
} else if (points[i].y == points[j].y) {
slope = 0.0;
} else {
slope = ((double)(points[i].y - points[j].y))/(points[i].x - points[j].x);
}
if (map.containsKey(slope)) {
map.put(slope, map.get(slope) + 1);
} else {
map.put(slope, 2);// two points form a line
}
}
for (Integer value : map.values()) {
localmax = Math.max(localmax, value);
}
localmax += duplicate;
max = Math.max(max, localmax);
map.clear();
}
return max;
}
}
Hope this helps,
Michael