1610. Maximum Number of Visible Points

──────────────────────────────────────────────────────────────────────

站在 location 這個位置，視野是 angle 度，可以原地旋轉但不能移動，問最多能同時看到幾個點。和自己重合的點不管轉到哪裡都看得到。

這個題目基本上屬於沒有寫過面試寫不太出來的問題，如果面試真的遇到這個題目，我是覺得這間公司基本上已經不想收人了⋯⋯

思路

題目的敘述很複雜，並且給出的例子並不是非常的好做推演，又題目給出一開始面向右側這個條件其實滿誤導人的，所以我花了時間重新理解了一下題目。

透過題目的例子，其實題目要找的就是在一個視角內，最多可以一次看到多少個目標。

那我們要怎麼樣知道一次最多可以看到幾個座標點呢？如果用圖形的角度來看的確是很簡單：首先我們可視範圍先對齊一個點，接著以自身為圓心，往左劃圓直到可視範圍角度的極限。以這個邏輯結構來看，我們會需要兩個參照座標，用來移動並更新可視範圍內的所有座標，就可以視題目為 Two Pointers 雙指針的題目。

但是困難的點是，多數的雙指針都是在線性的平面上面，可是這一題卻是在一個圓形／扇形的平面裡面。

所以整題的策略就是：先把圓形的東西攤成線性的東西，攤平之後就是一題普通的雙指針。 前面三個部分都在做這件事，真正的雙指針只有最後一段。

解題方向

class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        
        x0, y0 = location
        angles = []
        same = 0

        for x, y in points:
            dx, dy = x - x0, y - y0
            if dx == 0 and dy == 0:
                same += 1
                continue
            deg = math.degrees(math.atan2(dy, dx))
            angles.append(deg)
        
        angles.sort()

        extended = angles + [a + 360 for a in angles]

        counts = 0
        slow = 0
        fast = 0

        while slow < len(angles):
            while fast < len(extended) and extended[fast] - extended[slow] <= angle:
                fast += 1
            counts = max(counts, fast - slow)
            slow += 1
        
        return counts + same

一、把每個點換成角度

第一步是座標的轉換，這是一個在 LeetCode 裡面非常少用的 API，這個 API 是 math.atan2()（反正切函數）。除非日常工作是做影像視覺處理，不然這是一個日常軟體開發上很少用到的 API。

畢竟這是一個三角函數，所以就算知道它的意義，也還需要可以快速回憶起腦中對於三角函數的一些概念，不然接下來的邏輯也像是瞎子摸象。這裡簡單地說，就是要找出兩個點相對於水平線的夾角，並且帶著正負值，所以我們才能知道象限。

把八個方向都代一次，這個轉換長什麼樣子就很清楚了：

方向	`dx, dy`	`math.degrees(math.atan2(dy, dx))`
正右 →	`1, 0`	`0`
右上 ↗	`1, 1`	`45`
正上 ↑	`0, 1`	`90`
左上 ↖	`-1, 1`	`135`
正左 ←	`-1, 0`	`180`
左下 ↙	`-1, -1`	`-135`
正下 ↓	`0, -1`	`-90`
右下 ↘	`1, -1`	`-45`

正右邊是 0 度，逆時針為正、順時針為負，一路走到正左邊就是 180 度 —— 也就是 180 和 -180 撞在一起的那條分界線。這條線等一下會變成第三個難點。

拿題目的範例一走一遍：

location = (1, 1)，angle = 90

(2,1)   dx=1 dy=0   →    0 度
(2,2)   dx=1 dy=1   →   45 度
(3,3)   dx=2 dy=2   →   45 度

三個點全部落在 0 到 45 度之間，而視角有 90 度，所以一次就看得完，答案是 3。

這裡還可以看出一件事：(2,2) 和 (3,3) 的角度一模一樣，因為它們在同一條射線上，只是一遠一近。atan2 只保留方向、把距離丟掉了 —— 而這正是這個轉換成立的原因，因為距離對「看不看得到」本來就沒有影響。二維的點就這樣被壓成一維的角度。

二、和自己重合的點

這也是非常難想到的地方，是一個 edge case 需要處理：給的座標點清單中，有可能這些點和我們的起點相同。

這種情況下因為座標重複，並不需要旋轉就可以看得到，所以如果有座標跟我們所在的座標相同，就要記錄成一定可以看到的座標點，最後直接加回答案。

它們也不能留在 angles 裡面 —— 重合的點根本沒有角度可言（atan2(0, 0) 是沒有意義的）。

三、跨過 0 度的視角

這是第三個難點。atan2 轉出來的角度落在 -180 到 180 度之間，也就是說在 180 度／-180 度那條線上，圓被切開了。

舉例來說，一個點在 170 度、另一個點在 -170 度，它們在圖上其實只差 20 度，是緊鄰的兩個點；但排序之後，它們一個站在陣列頭、一個站在陣列尾。如果我的視角是 30 度，這兩個點應該要能一起被看到，可是線性的雙指針從頭掃到尾，永遠掃不到這個組合。

處理的方式就是把每個點都「多轉一圈」，也就是把每個角度加 360 度之後接在後面。在多轉一圈之前，還要先把每個角度從小到大排序好，這樣我們在轉動視角的時候，才可以確定相近角度的點都會一起被考慮到。

angles   = [-170, 170]
extended = [-170, 170, 190, 530]
                  └───┘
              170 和 190 只差 20 度，變成陣列裡相鄰的兩個數

那個 -170 度的點以 190 度的身分再出現了一次，圓就這樣被攤成了一條線。

四、雙指針展開視角

前面三個部分處理完後，我們會得到

哪些是和原點重複的座標
在座標平面上，每一個點其相對於原點的角度

一直到這裡，才會是題目解題的雙指針核心：

        counts = 0
        slow = 0
        fast = 0

        while slow < len(angles):
            while fast < len(extended) and extended[fast] - extended[slow] <= angle:
                fast += 1
            counts = max(counts, fast - slow)
            slow += 1
        
        return counts + same

這裡有另一個容易卡住的點，那就是快慢指針要怎麼處理。如同前面一開始所提，我們是定好一個位置後，接著開始展開視角直到極限為止，因此展開的時候是快指針去走。

另外一個點是，快指針在慢指針移動的時候，是否要重新從慢指針開始出發？答案是不用的。

如果快指針所指向的位置，在接下來幾個慢指針前進的時候都無法向前，那慢指針就會持續前進，這並不影響現階段的計數。
如果快指針可以繼續走，那當下慢指針跟快指針的距離可以更大，代表有更多的座標可以被加入，這樣也是可行的。

慢指針只跑 len(angles) 而不是 len(extended)，因為視角的左邊界只需要對齊「原本的每一個點」試一次就夠了，後面那一圈是複製品。

補充

這題如果真的在面試出現，好心一點的面試官會直接給你 math.atan2() 這個 API，然後告訴你它的意義是什麼 —— 因為這個 API 本身不是這題要考的東西，考的是後面把圓攤成線的那一步。

複雜度

時間 $O (n \log n)$ — 主要是排序的地方；雙指針那段快慢指針各只單向走過 extended 一次，是 $O (n)$
空間 $O (n)$ — angles 和 extended 各存一份角度

其中 $n$ 是 points 的數量。