1610. Maximum number of visible points: Polar Angle geometry problem

Topic describes

This is 1610 on LeetCode. The maximum number of visible points, difficulty is difficult.

Tag: “Math”, “Geometry”, “Sort”, “double pointer”, “sliding window”

Given a set of points and an integer Angle, your position is location. Location =[posx,posy]location =[pos_x, pos_y]location=[posx,posy] location=[posx,posy] and points[I]=[xi,yi]points[I]=[x_i, Y_i]points[I]=[xi,yi] are integer coordinates on the X-y plane.

At first, you look east. You can’t move around to change your position, but you can adjust your viewing Angle by rotating. In other words, posxPOS_xposx and Posypos_yposy cannot be changed. The Angle of your field of view is indicated by Angle, which determines how wide you can view in any direction. If d is the number of degrees you rotate counterclockwise, then your view is the area indicated by the range [D − Angle /2,d+ Angle /2][D-angle /2,d+ Angle /2].

For each point, you can see it if the Angle formed by that point, your position, and the direction directly east from your position is in your field of vision.

You can have multiple points on the same coordinate. There may be points where you are, but no matter how you rotate, you will always see them. At the same time, points don’t block you from seeing other points.

Returns the maximum number of points you can see.

Example 1:

Points = [[2,1],[2,2],[3,3]], Angle = 90, location = [1,1] In your field of vision, all the points are clearly visible, and you can still see [3,3] even though [2,2] and [3,3] are on the same line.Copy the code

Example 2:

Input: points = [[2,1],[2,2],[3,4],[1,1]], Angle = 90, location = [1,1] output: 4 explanation: in your field of vision, all points are clearly visible, including the point where you are.Copy the code

Example 3:

Input: points = [[1,0],[2,1]], Angle = 13, location = [1,1] output: 1 explanation: as shown in the figure, you can only see one of two points.Copy the code

Tip:

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

mathematics

This is a difficult thinking, but many details of the topic.

They want us to rotate an infinitely extensible coverage Angle of AngleAngleAngle so that it covers as many points in the Pointspointspoints as possible.

Location =(x,y)location =(x,y)location =(x,y) (x,y) Points [I]points[I]points[I]

Make points [I] = (a, b) points [I] = (a, b) points [I] = (a, b), relationship between pole dx = a – x; Dy =b−ydx = a-x; Dy = b-ydx =a−x; Dy = b – y.

There are two ways to find the polar Angle:

1. Use the atan (dydx) atan (\ frac {dy} {dx}) atan (dx dy) : The range of the range is [-90°,90°], it is necessary to discuss the quadrants of DXDXDX and dydydy, so as to transform the range of the range into the desired [0°,360°], and pay attention to the boundary of dx=0dx =0dx =0;

2. Atan2 (dy,dx)atan2(dy, dx) : the range of the value is [-180°,180°], and we expect [0°,360°] a fixed value, can be unified conversion, can also be directly used.

After obtaining the included Angle array ListListList, sort it, and the problem is initially converted into: List [I]list[I]list[I]list[I]list[I]list[I]list[I]list[j]list[j] list[j]list[j]list[j] list[j]list[j]list[j] list[j]list[j]list[j] list[j]list[j]list[j] list[j]list[j]

But operating directly on the original array listListList would miss the case where the Angle spans one quadrant:

Therefore, another detail is that when calculating the length of the contiguous segment, we first copy and concatenate the Angle array and increase the offset of the concatenated portion (to ensure that the array is still monotonic).

Specifically, set the length of the included Angle array as NNN, and make list[n+ I]=list[I]+2∗PIlist[n + I]=list[I]+2 * PIlist[n+ I]=list[I]+2∗PI, so as to completely transform the problem into the problem of obtaining continuous segments.

To solve the longest legal continuous segment [I,j][I,j][I,j] can be done by “double pointer” realization of “sliding window”.

Some details: They specify that the points that coincide with locationLocationLocation can be seen from any Angle, so we need to do special treatment for those points,

Code:

class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        int x = location.get(0), y = location.get(1);
        List<Double> list = new ArrayList<>();
        int cnt = 0;
        double pi = Math.PI, t = angle * pi / 180;
        for (List<Integer> p : points) {
            int a = p.get(0), b = p.get(1);
            if (a == x && b == y && ++cnt >= 0) continue;
            list.add(Math.atan2(b - y, a - x) + pi);
        }
        Collections.sort(list);
        int n = list.size(), max = 0;
        for (int i = 0; i < n; i++) list.add(list.get(i) + 2 * pi);
        for (int i = 0, j = 0; j < 2 * n; j++) {
            while (i < j && list.get(j) - list.get(i) > t) i++;
            max = Math.max(max, j - i + 1);
        }
        returncnt + max; }}Copy the code

• Time complexity: let
  $n$ 为 pointsArray length, preprocessed outpointsThe complexity of all angles of is
  $O(n)$; The complexity of sorting all angles is
  $O(n\log{n})$; The complexity of maximum legal subarray is obtained by using double pointer to realize sliding window
  $O(n)$; The overall complexity is
  $O(n\log{n})$
• Space complexity: O(n)O(n)O(n)

The last

This is the No.1610 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.