master
1description = <<-DOC
2Given an array of points on a 2D plane, find the maximum number of points that are visible from point (0, 0) with a viewing angle that is equal to 45 degrees.
3
4Example
5
6For
7
8 points = [[1, 1], [3, 1], [3, 2], [3, 3],
9 [1, 3], [2, 5], [1, 5], [-1, -1],
10 [-1, -2], [-2, -3], [-4, -4]]
11the output should be visiblePoints(points) = 6.
12
13This visualization shows how these 6 points can be viewed:
14
15
16
17Input/Output
18
19[time limit] 4000ms (rb)
20[input] array.array.integer points
21
22The array of points. For each valid i, points[i] contains exactly 2 elements and represents the ith point, where points[i][0] is the x-coordinate and points[i][1] is the y-coordinate. It is guaranteed that there are no points located at (0, 0) and there are no two points located at the same place.
23
24Guaranteed constraints:
251 ≤ points.length ≤ 105,
261 ≤ points[i].length = 2,
27-107 ≤ points[i][j] ≤ 107.
28
29[output] integer
30
31The maximum number of points that can be viewed from point (0, 0) with a viewing angle that is equal to 45 degrees.
32
33NOTES
34
35Vertex is always (0, 0)
36
37Pythagorean theorem.
38
39* right triangle has 90 degrees
40* sum of all angles inside a triangle = 180 degrees
41
42If we know two sides of a right triangle we can find the third side.
43
44Hypotenuse: Long side is opposite the right angle.
45
46A^2 + B^2 = C^2
47C is the hypotenuse
48
49Trigonometric Functions
50
51Soh Cah Toa
52sine(degrees) = Opposite (length) / Hypotenuse (length)
53cosine(degrees) = Adjacent (length) / Hypotenuse (length)
54tangent(degrees) = Opposite (length) / Adjacent (length)
55
56
57Inverse Trigonometric Functions
58
59sin(x) = O/H ===> x = sin-1(O/H) (inverse sine aka arcsin)
60cos(x) = A/H ===> x = cos-1(A/H) (inverse cos aka arccos)
61toa(x) = O/A ===> x = tan-1(O/A) (inverse tan aka arctan)
62
63arctan(35/65) = 28.3 degrees
64
65Math.atan(35.0/65.0) * (180 / Math::PI)
66=> 28.300755766006375
67
68DOC
69
70describe "visible points" do
71 def radians_to_degrees(radians)
72 radians * (180 / Math::PI)
73 end
74
75 def degrees_to_radians(degrees)
76 degrees * (Math::PI / 180)
77 end
78
79 def angle_for(x, y)
80 degrees = radians_to_degrees(Math.atan(y.abs.to_f / x.abs.to_f))
81 return degrees if x >= 0 && y >= 0 # quadrant 1
82 return degrees + 90 if x < 0 && y > 0 # quadrant 2
83 return degrees + 180 if x <= 0 && y <= 0 # quadrant 3
84 return degrees + 270 if x > 0 && y <= 0 # quadrant 4
85
86 raise [x, y].inspect
87 end
88
89 def visible_points(points, viewing_angle: 45)
90 angles = points.map { |(x, y)| angle_for(x, y) }.sort
91 t = max = counter = 0
92 flag = false
93 angles.size.times do |h|
94 head = angles[h]
95 loop do
96 tail = angles[t]
97 tail += 360 if t < h
98
99 break if tail < head || tail > (head + viewing_angle)
100 break if t == h && flag
101
102 counter += 1
103 t += 1
104
105 if t == angles.size
106 t = 0
107 flag = true
108 end
109 end
110 max = counter if counter > max
111 counter -= 1
112 end
113 max
114 end
115
116 it do
117 points = [
118 [29, 12], # 22.48 degrees
119 [36, -99], # 340.02 degrees (360 - 340.02 = 19.98)
120 ]
121 expect(visible_points(points)).to eql(2)
122 end
123
124 it do
125 points = [[1, 1], [3, 1], [3, 2], [3, 3], [1, 3], [2, 5], [1, 5], [-1, -1], [-1, -2], [-2, -3], [-4, -4]]
126 expect(visible_points(points)).to eql(6)
127 end
128
129 it do
130 points = [[1,1], [3,1], [3,2], [3,3], [1,3], [2,5], [1,5], [-1,-1], [-1,-2], [-2,-3], [-4,-4]]
131 expect(visible_points(points)).to eql(6)
132 end
133
134 it do
135 points = [[5,4]]
136 expect(visible_points(points)).to eql(1)
137 end
138
139 it do
140 points = [[3,0], [-2,2]]
141 expect(visible_points(points)).to eql(1)
142 end
143
144 it do
145 points = [[-2,2], [-2,-2], [-5,0]]
146 expect(visible_points(points)).to eql(2)
147 end
148
149 it do
150 points = [[3,3], [-4,4], [-2,-2], [1,-1], [10,-10]]
151 expect(visible_points(points)).to eql(2)
152 end
153
154 it do
155 points = [[27,-88], [76,56], [-82,62], [-5,48], [-85,60], [-86,6], [-100,-54], [-22,30], [58,47], [12,80]]
156 expect(visible_points(points)).to eql(3)
157 end
158
159 it do
160 points = [[1, 0], [0, 1], [-1, 0], [0, -1]]
161 expect(visible_points(points)).to eql(1)
162 end
163
164 it 'returns 135' do
165 expect(angle_for(-2, 2)).to eql(45.0 + 90.0)
166 end
167
168 it 'returns 180' do
169 expect(angle_for(-5, 0)).to eql(180.0)
170 end
171
172 it 'returns 0' do
173 expect(angle_for(1, 0)).to eql(0.0)
174 end
175
176 it 'returns 90' do
177 expect(angle_for(0, 1)).to eql(90.0)
178 end
179
180 it 'returns 180' do
181 expect(angle_for(-1, 0)).to eql(180.0)
182 end
183
184 it 'returns 270' do
185 expect(angle_for(0, -1)).to eql(270.0)
186 end
187
188 it 'spec_name' do
189 [
190 [1, 0, 0.0],
191 [1, 1, 45.0],
192 [0, 1, 90.0],
193 [-1, 1, 135.0],
194 [-1, 0, 180.0],
195 [-1, -1, 225.0],
196 [0, -1, 270.0],
197 [1, -1, 315.0]
198 ].each do |(x, y, expected)|
199 expect(angle_for(x, y)).to eql(expected)
200 end
201 end
202
203 it do
204 angles = Set.new
205 -100.upto(100) do |x|
206 -100.upto(100) do |y|
207 next if x == 0 && y == 0
208 angle = angle_for(x, y).floor
209 angles << angle
210 end
211 end
212 expect(angles.count).to eql(360)
213 end
214end