<p>You are given an array <code>points</code>, an integer <code>angle</code>, and your <code>location</code>, where <code>location = [pos<sub>x</sub>, pos<sub>y</sub>]</code> and <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> both denote <strong>integral coordinates</strong> on the X-Y plane.</p>

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

<p>
<video autoplay="" controls="" height="360" muted="" style="max-width:100%;height:auto;" width="480"><source src="https://assets.leetcode.com/uploads/2020/09/30/angle.mp4" type="video/mp4" />Your browser does not support the video tag or this video format.</video>
</p>

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

<p>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.</p>

<p>Return <em>the maximum number of points you can see</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/30/89a07e9b-00ab-4967-976a-c723b2aa8656.png" style="width: 400px; height: 300px;" />
<pre>
<strong>Input:</strong> points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
<strong>Output:</strong> 4
<strong>Explanation:</strong> All points can be made visible in your field of view, including the one at your location.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/30/5010bfd3-86e6-465f-ac64-e9df941d2e49.png" style="width: 690px; height: 348px;" />
<pre>
<strong>Input:</strong> points = [[1,0],[2,1]], angle = 13, location = [1,1]
<strong>Output:</strong> 1
<strong>Explanation:</strong> You can only see one of the two points, as shown above.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= points.length &lt;= 10<sup>5</sup></code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>location.length == 2</code></li>
	<li><code>0 &lt;= angle &lt; 360</code></li>
	<li><code>0 &lt;= pos<sub>x</sub>, pos<sub>y</sub>, x<sub>i</sub>, y<sub>i</sub> &lt;= 100</code></li>
</ul>

class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        '''
        Problem:
        points = List of [x,y]
        location = [x,y]
        integral coords
        
        facing east, cannot move, can rotate
        angle = field of view = [d-angle/2, d+angle/2] if d = rotation

        can see point if angle from point to location to east is in fov
            ignore sightlines
        points can overlap
        point at location can be seen (fov is inclusive)

        return max num points seen

        assume angle = [0,360]
        assume coords are non negative ints
        '''
        '''
        Approach:
        calculate angle of a point
        calculate angle window of fov
        sort points by angle
        slide fov window along points, keeping track of max size of window
        '''
        # Helper function to convert a point to an angle
        def get_angle(origin, point):
            x = point[0] - origin[0]
            y = point[1] - origin[1]
            rad_angle = math.atan2(y, x) # converts x,y to angle
            deg_angle = rad_angle * (180 / math.pi)
            angle = deg_angle if deg_angle >= 0 else deg_angle + 360
            return angle

        # Track points that overlap with location
        always_visible = 0
        # Convert points to angles and sort
        point_angles = []
        for point in points:
            # handle points overlapping with location
            # don't use in list bc they are always visible
            if point == location:
                always_visible += 1
            else:
                point_angles.append(get_angle(location, point))
        point_angles.sort()

        # skip if we don't have any non overlapping points
        if not point_angles:
            return always_visible

        # handle rollover when we approach point angle == 0
        max_angle = point_angles[-1]
        for point_angle in point_angles:
            rollover_angle = point_angle + 360
            # only include angles with will be visible including the last point
            if rollover_angle > max_angle + angle:
                break
            point_angles.append(rollover_angle)

        # track max window size, representing max num points seen in a view
        max_num_points = 0
        # sliding window to represent fov
        left_index = 0
        right_index = 0

        # check through all possible points
        while right_index < len(point_angles):
            right_point = point_angles[right_index]
            left_point = point_angles[left_index]
            # if the range of points within view, add points
            if right_point-left_point <= angle:
                # record num points if appropriate
                max_num_points = max(max_num_points, 1+right_index-left_index)
                right_index += 1
            # if new point is beyond our fov, remove earlist point to represent rotating
            else:
                left_index += 1
        return max_num_points + always_visible

50300