# 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