題目：Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
答案：
import java.util.*;
/**
* 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) {
int length = points.length;
if(length<3)
return length;
int max = 2;
for(int i=0; i<length; i++) {
int pointMax = 1;
int samePoints = 0;
Point start = points[i];
HashMap<Double, Integer> map = new HashMap<Double, Integer> ();
for(int j=i+1; j<length; j++){
Point end = points[j];
if(start.x == end.x && start.y == end.y) {
samePoints++;
continue;
}
double k;
if(start.x == end.x) {
k = Float.POSITIVE_INFINITY;
}else if(start.y == end.y) {
k = 0;
}else{
k = (float)(start.y-end.y)/(start.x-end.x);
}
if(map.containsKey(k)) {
map.put(k, map.get(k)+1);
}else{
map.put(k,2);
}
pointMax = Math.max(pointMax, map.get(k));
}
pointMax += samePoints;
max = Math.max(max, pointMax);
}
return max;
}
}
