旋轉卡尺

tags: Competitive Programming Note 108 師大附中校隊培訓

本文已停止更新，新版請至 WiwiHo 的競程筆記

108 師大附中校隊培訓簡報

用旋轉兩條平行線、夾住一堆點，看在線上的點是哪些，就叫旋轉卡尺。

旋轉線、夾點感覺很麻煩，是不是要用到什麼角度的東西啊？其實不用，先來分析一下問題，用兩條平行線夾一堆點，那麼平行線只會碰到凸包上的點而已，所以不在凸包上的點都可以先忽略：

過一個點的直線有很多條，但是過一個線段的直線只有一條，所以先枚舉線段，再去找和它平行的直線應該會夾到哪個點，這樣問題就簡單多了。要找平行線會碰到哪個點，顯然離線段最遠的點就是了。

不過算距離是另一個問題，聽起來也很麻煩，但其實很簡單。一個點距離一條直線的距離，等同於過該點在直線上作垂線段的長，而一開始選定的線段作為底、垂線段長作為高，那麼就可以得到一個平行四邊形面積了，且底的長是固定的，只要枚舉最遠點，就等同於枚舉高，而得出面積最大的，就是我們要的最遠點了。

上圖中，選定兩個紅色點所連成的線段為底，然後枚舉各個頂點取高，得出藍色垂線是最長的，因此藍色點就是距離紅色線段最遠的點。

這就是旋轉卡尺的基礎應用——最遠點對，找到距離每一線段最遠的點，再取該點與線段兩端點的距離取最大值，這樣就可以得出所有點中最遠的點對為何。

硬要這麼做的方式，時間複雜度是

$O(N^2)$，

$N$ 是凸包上點的數量（不計蓋凸包的複雜度），枚舉線段是

$O(N)$，再枚舉一個點要再乘上

$O(N)$。

這不夠快，我們需要更有效率的方式。

仔細觀察一下，點和線段的距離有一個規律——先漸大，到一個最大值，再漸小：

我們發現它會呈現一個單峰函數，也就是一個先遞增、再遞減的函數，這樣我們就可以用三分搜找到最高點了，這樣三分搜一次的複雜度是

$O(\log N)$，再乘上點的數量，就是

$O(N\log N)$。

這樣子還是不夠快，前面提到旋轉卡尺是「旋轉兩條平行線」，剛剛的動作都是旋轉其中一條，再去搜尋另一條，那我們可不可以在旋轉其中一條的同時，把另一條一起旋轉？答案是：可以。

（以下的轉都是指往同一個方向轉）
先找到距離第一條邊最遠的點，過前者的線稱為第一條平行線，過後者的稱為第二條平行線，接下來我們轉動第一條平行線，也就是把它轉到第二條線段上，而第二條平行線不要動，會發現，第一條平行線離第二條平行線那個點近了一些，接著再轉第二條平行線，也就是把它轉到下一個點上，那麼距離會變遠。

也就是，可以在不重新來過的情況下，找到單峰函數的最高點，會發現這樣就是把兩條平行線繞一圈，因此這樣的複雜度是

$O(N)$。

最大三角形

給你一堆點，請找出這些點所能構成的面積最大的三角形。

用類似最遠點對的想法來想，先

$O(N^2)$ 枚舉兩個頂點，然後再用旋轉卡尺去找第三個頂點。首先，先枚舉第一個點，然後在枚舉第二個點的同時，第三個點可以跟著往下轉，這樣就可以

$O(N^2)$ 解決這件事。

練習題

• ZeroJudge b288 - 最大三角形
• TIOJ 1105 - 最遠點對