1 package com.lw.leet3;  2   3 import java.util.HashMap;  4 import java.util.Iterator;  5 import java.util.Map;  6 import java.util.Map.Entry;  7   8   9 /** 10  * @ClassName:Solution 11  * @Description:Max Points on a Line  12  *         Given n points on a 2D plane, find the maximum number of points that  13  *         lie on the same straight line. 14  * @Author LiuWei 15  * @Date 2014年8月17日下午2:51:08 16  * @Mail nashiyue1314@163.com  17  */ 18  19 /** 20  * Definition for a point. 21  * class Point { 22  *     int x; 23  *     int y; 24  *     Point() { x = 0; y = 0; } 25  *     Point(int a, int b) { x = a; y = b; } 26  * } 27  */ 28  29 public class Solution { 30  31     public int maxPoints(Point[] points) { 32         int max = 0; 33         if(points.length <= 2){ 34             max = points.length; 35         } 36         else{ 37             for(int i = 0; i < points.length; i++){ 38                 int equalNum = 0; 39                 Map
     
       map = new HashMap
      
       (); 40                 for(int j = i+1; j < points.length; j++ ){ 41                     if(points[i].x == points[j].x && points[i].y == points[j].y){ 42                         equalNum ++; 43                         continue; 44                     } 45                      46                     double k = 0; 47                     if(points[i].x == points[j].x){ 48                         k = Double.MAX_VALUE; 49                     } 50                     else{ 51                         k = ((double)(points[i].y - points[j].y)/(points[i].x - points[j].x)); 52                         /** 53                          * Submission Result: Wrong Answer 54                          * Input:    [(2,3),(3,3),(-5,3)] 55                          * Output:    2 56                          * Expected:3 57                          *  58                          * avoid k = +0.0 -0.0 59                          * */ 60                         if(k == 0){ 61                             k = 0;  62                         } 63                     } 64                      65                     if(map.containsKey(k)){ 66                         map.put(k, map.get(k)+1); 67                     } 68                     else{ 69                         map.put(k, 2); 70                     } 71                 } 72                  73                 /** 74                  * Submission Result: Wrong Answer 75                  * Input:    [(1,1),(1,1),(1,1)] 76                  * Output:    0 77                  * Expected:3 78                  *  79                  * avoid the points are all equal 80                  * */ 81                 if(equalNum > max){ 82                     max = equalNum + 1 ; 83                 } 84                 Iterator
       
        
         > iter = map.entrySet().iterator(); 85                 while(iter.hasNext()){ 86                     Entry
         
           entry = iter.next(); 87                     int num = entry.getValue(); 88                     if( num + equalNum > max){ 89                         max = num + equalNum;  90                     } 91                 } 92             } 93         } 94         return max; 95     } 96      97     public static void main(String[] args){ 98         Point[] p = {
   new Point(2, 3),new Point(3,3),new Point(-5,3)}; 99 //        Point[] p = {new Point(1, 1),new Point(1,1),new Point(1,1)};100         101         Solution s = new Solution();102         System.out.println(s.maxPoints(p));103         104     }105     106 }