“This is the 23rd day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

describe

You are given an array points, an integer angle, and your location, where location = [posx, posy] and points[i] = [xi, yi] both denote integral coordinates on the X-Y plane.

Initially, you are facing directly east from your position. You cannot move from your position, but you can rotate. In other words, posx and posy cannot be changed. Your field of view in degrees is represented by angle, determining how wide you can see from any given view direction. Let d be the amount in degrees that you rotate counterclockwise. Then, your field of view is the inclusive range of angles [d – angle/2, d + angle/2].

You can see some set of points if, for each point, the angle formed by the point, your position, and the immediate east direction from your position is in your field of view.

There can be multiple points at one coordinate. There may be points at your location, and you can always see these points regardless of your rotation. Points do not obstruct your vision to other points.

Return the maximum number of points you can see.

Example 1:

Input: points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
Output: 3
Explanation: The shaded region represents your field of view. All points can be made visible in your field of view, including [3,3] even though [2,2] is in front and in the same line of sight.
Copy the code

Example 2:

Input: points = [[2,1],[2,2],[3,4], Angle = 90, location = [1,1] Output: 4 Explanation: All points can be made visible in your field of view, including the one at your location.Copy the code

Example 3:

Input: points = [[1,0],[2,1]], angle = 13, location = [1,1]
Output: 1
Explanation: You can only see one of the two points, as shown above.
Copy the code

Note:

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • location.length == 2
  • 0 <= angle < 360
  • 0 <= posx, posy, xi, yi< = 100

parsing

Give a list points, an integer Angle, and your location, where location = [posx, posy] and points[I] = [xi, yi] represent integral coordinates on the X-y plane.

Initially, stand your position directly facing east. You can’t move from your position, but you can rotate. In other words, POSx and POSy cannot change. The view in degrees is represented by Angle, which determines the width that can be seen from any given line of sight direction. Let d represent the degree by which you rotate counterclockwise. Then, your view is the inclusion range of the Angle [D-angle /2, D + Angle /2].

If for each point, the Angle formed by that point, your position, and directly east from your position is in your field of view, you can see a collection of points. You can have multiple points on one coordinate. There may be points in your position that you can always see no matter how you rotate. A point does not interfere with your view of the other points. Returns the maximum number of points you can see.

In fact, after reading this question is relatively simple, the general idea is to take location as the origin, and then calculate the Angle formed by each point in points and the origin, and record it in angles, and then use the sliding window idea to find the point with the most points within the Angle range. There are two points to note:

  • The first is to calculate the included Angle, which needs to be noted that the range is [0, 2* PI], but there may be angles in the vicinity of 0 degree that meet the meaning of the question. Therefore, the value of angles plus 2* PI needs to be extended after angles, which can represent the range of [2* PI, 4* PI]
  • The second is the accuracy of decimals, we must consider in place, after all, the computer is floating point when calculating the included Angle, the accuracy is not enough to find points may appear error
  • The third one is that there are points at the origin, points that are always visible, and you just add them to the result

answer

class Solution(object): def visiblePoints(self, points, angle, location): """ :type points: List[List[int]] :type angle: int :type location: List[int] :rtype: Angles = [] Angle = 0 for x, y in points: dx = x - location[0] dy = y - location[1] if dx == 0 and dy == 0: origin += 1 continue alpha = atan2(dy, dx) + pi angles.append(alpha) angles.sort() N = len(angles) for i in range(N): angles.append(angles[i] + 2 * pi) result = j = 0 for i in range(2*N): Angles [I] <= Angle * 1.0 * PI / 180 + 0000001: j += 1 result = max(result, j - i) return result + originCopy the code

The results

Given in the Python online submissions. Memory Usage: 10000 10000 ms Submissions in Python online submissions for Maximum Number of Visible Points.Copy the code

Original link: leetcode.com/problems/ma…

Your support is my biggest motivation