1610. Maximum Number of Visible Points

Problem

You are given an array points, an integer angle, and your location, where location = [pos_x, pos_y] and points[i] = [x_i, y_i] 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, pos_x and pos_y 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.

https://leetcode.com/problems/maximum-number-of-visible-points/

Example 1:

case1

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.

Example 2:

Input: points = [[2,1],[2,2],[3,4],[1,1]], 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.

Example 3:

case3

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.

Constraints:

1 <= points.length <= 10⁵
points[i].length == 2
location.length == 2
0 <= angle < 360
0 <= pos_x, pos_y, x_i, y_i <= 100

Test Cases

1 2	class Solution: def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('points, angle, location, expected', [
    ([[2,1],[2,2],[3,3]], 90, [1,1], 3),
    ([[2,1],[2,2],[3,4],[1,1]], 90, [1,1], 4),
    ([[1,0],[2,1]], 13, [1,1], 1),

    (
        [[65,14],[94,87],[17,50],[70,10],[69,14],[38,1],[4,72],[8,5],[5,77],[97,82],[89,34],[70,43],[15,98],[66,7],[39,15],[21,58],[8,70],[41,56],[36,70],[79,50],[3,90],[90,26],[36,31],[12,10],[98,88],[26,60],[3,94],[0,49],[61,15],[73,41],[28,79],[10,80],[47,25],[74,7],[94,5],[70,9],[28,69],[92,60],[61,35],[17,86],[60,85],[53,50],[41,85],[26,98],[54,90],[26,65],[100,59],[47,50],[76,82],[48,20],[68,73],[40,8],[49,60],[92,45],[83,30],[59,1],[54,34],[68,20],[21,16],[48,60],[61,2],[0,53],[9,10],[7,81],[4,13],[42,60],[68,26],[63,14],[26,17],[52,34],[58,65],[74,52],[83,70],[98,89],[53,37],[39,43],[83,76],[58,8],[50,12],[4,99],[98,67],[72,24],[91,58],[49,5],[46,67],[22,90],[100,73],[50,12],[16,97],[41,63],[72,71],[71,5],[30,60],[77,71],[5,68],[43,92],[46,11],[76,40],[60,20],[30,83],[63,18],[45,50],[50,84],[32,99],[15,84],[77,92],[16,88],[36,42],[13,64],[91,59],[19,96],[3,15],[93,88],[83,83],[61,88],[21,50],[61,94],[77,85],[74,30],[43,32],[88,72],[32,17],[89,74],[60,40],[5,43],[30,19],[0,13],[54,65],[98,14],[49,91],[77,11],[42,12],[96,29],[65,61],[45,4],[3,72],[46,97],[33,97],[92,28],[0,4],[62,48],[94,13],[1,11],[28,73],[50,32],[47,40],[28,8],[90,51],[24,40],[56,23],[38,72],[12,84],[14,27],[91,8],[21,44],[55,90],[42,73],[86,62],[4,63],[24,60],[12,57],[90,25],[50,89],[1,85],[63,1],[68,93],[76,74],[80,8],[55,56],[85,77],[87,50],[98,25],[78,94],[26,45],[91,34],[89,60]],
        227,
        [60,100],
        176
    )
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, points, angle, location, expected):
    assert sol.visiblePoints(points, angle, location) == expected

Thoughts

首先做坐标系变换，从原直角坐标系，变换到以 location 为原点的极坐标系。极坐标系下，一个点的坐标是 (r, θ)。对于 r = 0 的点，与观察者重合，始终都可以看得到，可以单独记录下有多少个。

根据直角坐标 (x, y) 计算极坐标 θ，用 math.atan2 函数，其值域为 (-π, π]。

r ≠ 0 的所有点按 θ 排序，就是个滑动窗口的问题。

比一般滑动窗口稍微复杂一点儿的是数组是首尾相接的，而且每循环一次，所有的 θ 都要加上 2 π。用 Python 的话，range(-n, n) 刚好可以遍历数组两遍。

而且并不需要完整遍历两次，实际上只需要对旋转角度 d 取 [0, 360° + angle]（或者说 [-360°, angle]）即可。

另外像 2779. Maximum Beauty of an Array After Applying Operation 最后提到的优化点，窗口在滑动过程中可以只增不减，用自身记录可行窗口的最大大小。

时间复杂度 O(n log n)，空间复杂度 O(n)。

Code

solution.py

from math import atan2, pi, radians


class Solution:
    def visiblePoints(self, points: list[list[int]], angle: int, location: list[int]) -> int:
        overlap = 0
        thetas = []
        for x, y in points:
            if x == location[0] and y == location[1]:
                overlap += 1
            else:
                thetas.append(atan2(y - location[1], x - location[0]) - pi) # (-2pi, 0]

        if not thetas: return overlap

        pi2 = 2 * pi
        fov = radians(angle)
        thetas.sort()
        n = len(thetas)
        l = -n
        theta_l = thetas[l]
        for r in range(1 - n, n):
            theta_r = thetas[r] if r < 0 else thetas[r] + pi2
            if theta_r > fov: break
            if theta_r - theta_l > fov:
                l += 1
                theta_l = thetas[l] if l < 0 else thetas[l] + pi2
        else:
            r = n

        return overlap + r - l