1 public class Solution { 2 public int maxPoints(Point[] points) { 3 HashMap<Double,Integer> map = new HashMap<Double,Integer>(); 4 int res = 0; 5 for(int i=0;i<points.length;i++){ 6 map.clear(); 7 int curMax = 1; 8 int sameP =0; 9 for(int j=i+1;j<points.length;j++){ 10 double slop = Double.MAX_VALUE; 11 if(points[i].x==points[j].x && points[j].y==points[i].y){ 12 sameP++; 13 continue; 14 } 15 else if(points[j].y==points[i].y){ 16 slop =0.0;//y1==y2 because double has -0.0 17 } 18 else if(points[i].x!=points[j].x && points[j].y!=points[i].y){ 19 slop = (1.0*(points[i].y-points[j].y)/(points[i].x-points[j].x)); 20 } 21 if(map.containsKey(slop)){ 22 int temp = map.get(slop); 23 map.put(slop,temp+1); 24 curMax = Math.max(curMax,temp+1); 25 } 26 else{ 27 map.put(slop,2); 28 curMax = Math.max(curMax,2); 29 } 30 } 31 res = Math.max(curMax+sameP,res); 32 } 33 return res; 34 } 35 }
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
原文:http://www.cnblogs.com/krunning/p/3563990.html