be careful when x1 = x2
1 /** 2 * Definition for a point. 3 * class Point { 4 * int x; 5 * int y; 6 * Point() { x = 0; y = 0; } 7 * Point(int a, int b) { x = a; y = b; } 8 * } 9 */ 10 public class Solution { 11 public int maxPoints(Point[] points) { 12 // IMPORTANT: Please reset any member data you declared, as 13 // the same Solution instance will be reused for each test case. 14 if(points == null || points.length == 0) 15 return 0; 16 int len = points.length; 17 int max = 1; 18 for(int i = 0; i < len; i++){ 19 Point point1 = points[i]; 20 for(int j = i+1; j<len; j++){ 21 Point point2 = points[j]; 22 int count = 0; 23 24 if(point1.x == point2.x) 25 for(int z = 0; z < len; z++){ 26 if(points[z].x == point1.x) 27 count++; 28 } 29 else 30 for(int z = 0; z < len; z++){ 31 double x1 = point1.x; 32 double y1 = point1.y; 33 double x2 = point2.x; 34 double y2 = point2.y; 35 double a = (y1 - y2) / (x1 - x2); 36 double b = (y1 * x2 - y2 * x1) / (x2 - x1); 37 if(Math.abs(points[z].x * a + b - points[z].y) < 0.000001) 38 count++; 39 } 40 if(count > max) 41 max = count; 42 } 43 } 44 return max; 45 } 46 }