By

文章目录

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {

		if(points.length<=1)
		{
			return points.length;
		}
		
		int[] pointNum=new int[points.length];//the number in average group
		Point[] pointGroup=new Point[points.length];
		int groupLength=0;
		boolean flagAdd=false;
		for(Point point:points)
		{
			flagAdd=false;
			for(int i=0;i<groupLength;i++)
			{
				if(pointGroup[i].x==point.x && pointGroup[i].y==point.y)
				{
					pointNum[i]++;
					flagAdd=true;
					break;
				}
			}
			
			if(!flagAdd)
			{
				pointGroup[groupLength]=point;
				pointNum[groupLength]=1;
				groupLength++;
			}
		}
		
		int maxNum=pointNum[0],tempNum=0;
		HashMap<Straight,Integer> straightMap=new HashMap<Straight,Integer>();
		
		for(int i=0;i<groupLength;i++)
		{
			for(int j=i+1;j<groupLength;j++)
			{
				tempNum=pointNum[i]+pointNum[j];
				Straight straight=new Straight(pointGroup[i],pointGroup[j]);
				
				if(straightMap.containsKey(straight))
				{
					continue;
				}else{
					straightMap.put(straight, 1);
				}
				
				for(int k=j+1;k<groupLength;k++)
				{
					if(straight.isIn(pointGroup[k]))
					{
						tempNum+=pointNum[k];
					}
				}
				
				if(maxNum<tempNum)
				{
					maxNum=tempNum;
				}
			}
		}
		
		return maxNum;
    }
	
	class Straight{
		
		private double _gradient;
		private double _intercept;
		
		public Straight(Point p1,Point p2)
		{
			if(p1.x==p2.x)
			{
				this._gradient=Double.NaN;
				
				this._intercept=p1.x;
				
				
			}else{
				this._gradient=(p2.y-p1.y)/(double)(p2.x-p1.x);
				this._intercept=p1.y-this._gradient*p1.x;
			}
		}
		
		public Straight(double gradient,double intercept)
		{
			this._gradient=gradient;
			this._intercept=intercept;
		}
		
		/**
		 * judge this point whether in this straight
		 * @param point
		 * @return
		 */
		public boolean isIn(Point point)
		{
			
			if(Double.isNaN(this._gradient))
			{
				return this._intercept==point.x;
			}
			return Math.abs(point.y-(this._gradient*point.x+this._intercept))<=1e-7;
		}
		
	}
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录