极坐标

极坐标 1610.可见点的最大数目

---

前情提要 1. atan2

import math

# 第一象限
point = [1, 1] 
print(math.atan(point[1] / point[0]) / math.pi * 180)  # 45
print(math.atan2(point[1], point[0]) / math.pi * 180)  # 45

# 第二象限
point = [-1, 1]
print(math.atan(point[1] / point[0]) / math.pi * 180)  # -45
print(math.atan2(point[1], point[0]) / math.pi * 180) # 135

# 第三象限
point = [-1, -1]
print(math.atan(point[1] / point[0]) / math.pi * 180)  # 45
print(math.atan2(point[1], point[0]) / math.pi * 180) # -135

# 第四象限
point = [1, -1]
print(math.atan(point[1] / point[0]) / math.pi * 180)  # -45
print(math.atan2(point[1], point[0]) / math.pi * 180)  # -45

---

2. bisect

l = [1, 4, 4, 6, 10]
print(bisect.bisect_left(l, 4))  # 1
print(bisect.bisect_left(l, 5))  # 3
print(bisect.bisect_right(l, 4))  # 3
print(bisect.bisect_right(l, 1))  # 1
print(bisect.bisect(l, 1))  # 1
print(bisect.bisect(l, 4))  # 3 
# bisect.bisect() is the same as bisect.bisect_right()

bisect.insort_left(l, 3) 
print(l)  # [1, 3, 4, 4, 6, 10]
bisect.insort_right(l, 5)  
print(l)  # [1, 3, 4, 4, 5, 6, 10]
bisect.insort(l, 4)  
print(l)  # [1, 3, 4, 4, 4, 5, 6, 10]
# bisect.insort() is the same as bisect.insort_right()

---

方法一：二分查找

class Solution(object):
    def visiblePoints(self, points, angle, location):
        polarDegrees = []  # 计算每个点和location的相对极坐标
        howManySame = 0
        Max = 0
        for point in points:
            if point == location:
                howManySame += 1
            else:
                x = point[0] - location[0]
                y = point[1] - location[1]
                polarDegree = atan2(y, x)  # y在前面，x在后面
                polarDegrees.append(polarDegree)
        polarDegrees.sort()
        polarDegrees += [deg + 2 * pi for deg in polarDegrees]  # 为什么要在这里加
        angle = angle * pi / 180  # 45 --> pi/4
        n = len(polarDegrees)
        for i in range(n):
            index = bisect_right(polarDegrees, polarDegrees[i] + angle) - i
            Max = max(index, Max)
        return Max + howManySame

for i in range(n):
    left, right = i, n - 1
    cur = polarDegrees[i] + angle
	while left < right:
        mid = (left + right + 1) // 2
        if polarDegrees[mid] > cur:
            right = mid - 1
        else:
            left = mid
	Max = max(right - i + 1, Max)

执行用时：1572 ms, 在所有 Python 提交中击败了16.67%的用户
内存消耗：46.9 MB, 在所有 Python 提交中击败了16.67%的用户

时间复杂度： O ( n log ⁡ n ) O(nlog n) O(nlogn)

---

方法二：滑动窗口

class Solution(object):
    def visiblePoints(self, points, angle, location):
        howManySame, Max = 0, 0
        polarDegrees = []
        for point in points:
            if point == location:
                howManySame += 1
            else:
                x = point[0] - location[0]
                y = point[1] - location[1]
                polarDegree = atan2(y, x)
                polarDegrees.append(polarDegree)
        polarDegrees.sort()
        # 追加2*pi
        n = len(polarDegrees)
        for i in range(n):
            polarDegrees += [polarDegrees[i] + 2 * pi]
        degree = angle * pi / 180   # 先/180再*pi报错
        right = 0
        for i in range(n):
            while right < n * 2 and polarDegrees[right] <= polarDegrees[i] + degree:
                right += 1
            Max = max(Max, right - i)
        return Max + howManySame

执行用时：456 ms, 在所有 Python 提交中击败了100.00%的用户
内存消耗：44 MB, 在所有 Python 提交中击败了16.67%的用户

时间复杂度： O ( n log ⁡ n ) O(nlog n) O(nlogn)