1 package leetcode; 2  3 import java.util.HashMap; 4  5 class Point{ 6     int x; 7     int y; 8     Point(){ 9         x=0;10         y=0;11     }12     Point(int a,int b){13         x=a;14         y=b;15     }16 }17 18 public class MaxPointOnALine {19     public static int maxPoints(Point[] points) {20         21         if(points.length<=2) {22             return points.length;23         }24         //斜率25         double k = 0.0;26         int maxPointNum      = 0;27         int parallelNum =0;28         int tempMaxPointNum  = 0;29         int sameNum=0;30         HashMap map=new HashMap<Double,Integer>();31         for(int i=0;i<points.length;i++){32             sameNum=1;33             parallelNum=0;34             tempMaxPointNum=0;35             map.clear();36             for(int j=i+1;j<points.length;j++){37                 if(points[i].x==points[j].x&&points[i].y==points[j].y){38                     sameNum++;39                 }40                 else if(points[i].x==points[j].x){41                     parallelNum++;42                     43                 }else {44                     if(points[i].y==points[j].y){45                         k=0.0;46                         47                     }else{48                         k=((double)(points[i].y-points[j].y))/(points[i].x-points[j].x);49                     }50                     if(map.get(k)==null){51                         map.put(k, new Integer(1));52                         if(1>tempMaxPointNum){53                             tempMaxPointNum=1;54                         }55                     }else{56                         int number=(int)map.get(k);57                         number++;58                         map.put(k, number);59                         if(number>tempMaxPointNum){60                             tempMaxPointNum=number;61                         }62                     }63                 }64             }65             if(parallelNum>1){66                 if(parallelNum>tempMaxPointNum)67                     tempMaxPointNum=parallelNum;68             }69             tempMaxPointNum+=sameNum;70             if(tempMaxPointNum>maxPointNum)71                 maxPointNum=tempMaxPointNum;72         }73         return maxPointNum;74     }75     public static void main(String[] args){76         Point[] parr = {new Point(1,1),new Point(1,2)};77         //maxPoints(parr);78         System.out.println(maxPoints(parr));79     }80 }