Problem statement

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

Solution

The idea is to sort points by polar angle - in python we can use function atan2, which given that coordinates of points no more than 100 will work fine in double domain. Then we use two pointers approach to find how many points we have in sliding window, also we add one more circle of shifted by 2pi points to our angles.

Complexity

Time complexity is O(n log n), space is O(n).

Code

class Solution:
    def visiblePoints(self, points, angle, L):
        points_cnt = Counter([(x,y) for x, y in points])
        shift = points_cnt[tuple(L)]
        A1 = sorted([atan2(y-L[1], x-L[0]) for x, y in points if (x, y) != tuple(L)])
        A2 = [a + 2*pi for a in A1]
        
        A, n, ans, end_index = A1 + A2, len(A1), 0, 0
        
        for i in range(n):
            border = A[i] + angle/180*pi
            while A[end_index] <= border: 
                end_index += 1
            ans = max(end_index - i, ans)
    
        return ans + shift

Remark

If we want to avoid rounding error and original points are integer, then we can use the following:

def quater(p):
    x, y = p
    if x >= 0 and y >= 0: return 2
    if x < 0 and y >= 0: return 1
    if x < 0 and y < 0: return 4
    if x >= 0 and y < 0: return 3

def compare(p1, p2):
    if quater(p1) == quater(p2):
        t1 = p1[1]*p2[0] - p2[1]*p1[0]
        return 0 if t1 == 0 else 1 if t1 > 0 else -1
    else:
        return 1 if quater(p1) < quater(p2) else -1

In this way points will be sorted from angle (-180, 180) without rounding errors. However in this specific problem we can not fully get rid of doubles, because we need to compare with angle, for which we need to evaluate tangent, and compare it with oriented angle between points. But for other angular sweep problem it can be useful.