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);
}
}