1610.可见点的最大数目

原题

参考题解

class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        x, y = location[0], location[1]
        angleList = []   #所有节点与观测者的夹角数组
        cnt = 0
        pi = math.pi
        for a, b in points:
            # 细节1：题目规定了与location重合的点在任意角度都能看到，因此我们需要对这些点进行特殊处理
            if a == x and b == y and (cnt+1) >= 0:
                cnt += 1
                continue
            # atan2值域[-180,180]与[0,360]相差pi
            angleList.append(math.atan2(b-y, a-x) + pi)
        # 双指针求数组中最长的连续序列
        t = angle * pi / 180
        angleList.sort()
        n = len(angleList)

        maxPoint = 0
        # 细节2：直接在原数组 listlist 操作，会漏掉夹角横跨一四象限的情况
        # 因此先对夹角数组进行拷贝拼接，并对拼接部分增加偏移量（确保数组仍具有单调性）
        for i in range(n):
            angleList.append(angleList[i] + 2*pi)
        i, j = 0, 0

        while j < 2*n:
            while i < j and angleList[j] - angleList[i] > t:
                i+= 1
            maxPoint = max(maxPoint, j-i+1)
            j += 1
        return cnt + maxPoint