学步园

题目：

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

解决：

[java] view
plaincopy

1. import java.util.HashMap;  
2. import java.util.Map;  
3.   
4. class Point {  
5.     int x;  
6.     int y;  
7.   
8.     Point() {  
9.         x = 0;  
10.         y = 0;  
11.     }  
12.   
13.     Point(int a, int b) {  
14.         x = a;  
15.         y = b;  
16.     }  
17. }  
18. /** 
19.  * 暴力破解： 
20.  * 遍历所有的点，每次取一个点，计算这个点与其他点斜率k，对k统计，找最大的。 
21.  * 注意相同的点， 水平或竖直同线的点。 
22.  * @author Administrator 
23.  * 
24.  */  
25. public class LinePoints {  
26.     public int maxPoints(Point[] points) {  
27.         if (points.length < 2)  
28.             return points.length;  
29.   
30.         int global_max = 0;  
31.   
32.         Map<Double, Integer> map_k = new HashMap<Double, Integer>();  
33.   
34.         for (int i = 0; i < points.length; i++) {//遍历，每次取一点A  
35.             int one_point_max = 0;  
36.             int h_max = 0;  
37.             int same_point_num = 0;  
38.             map_k.clear();  
39.   
40.             for (int j = 0; j < points.length; j++) {//计算点A与其他点的斜率k  
41.                 if (i == j) {// itself  
42.                     continue;  
43.                 } else {  
44.                     if (points[i].x == points[j].x  
45.                             && points[i].y == points[j].y) {// same point  
46.                         same_point_num++;  
47.                         continue;  
48.                     } else {  
49.                         if (points[i].x == points[j].x) {// 竖直同线的点  
50.                             h_max++;  
51.                             if (h_max > one_point_max)  
52.                                 one_point_max = h_max;  
53.                         } else {  
54.                             double k = 0;  
55.                             if (points[i].y == points[j].y)//水平同线的点  
56.                                 k = 0;  
57.                             else  
58.                                 k = ((double) (points[i].y - points[j].y))  
59.                                         / ((double) (points[i].x - points[j].x));  
60.   
61.                             int k_v = 1;  
62.                             Double dk = new Double(k);  
63.                             if (map_k.get(dk) != null) {  
64.                                 k_v = map_k.get(dk) + 1;  
65.                             }  
66.                             map_k.put(dk, new Integer(k_v));  
67.                             if (k_v > one_point_max)  
68.                                 one_point_max = k_v;  
69.                         }  
70.                     }  
71.   
72.                 }  
73.   
74.             }// end of for  
75.             if (one_point_max + same_point_num > global_max)  
76.                 global_max = one_point_max + same_point_num;  
77.   
78.         }// end of for  
79.   
80.         return global_max + 1;  
81.     }  
82.   
83.     public static void main(String[] args) {  
84.         LinePoints lp = new LinePoints();  
85.         Point[] points = new Point[2];  
86.         points[0] = new Point(0, 0);  
87.         points[1] = new Point(0, 0);  
88.   
89.         int s = lp.maxPoints(points);  
90.         System.out.println(s);  
91.     }  
92. }  

参考：

http://blog.csdn.net/worldwindjp/article/details/18882849