# 計算幾何：旋轉卡尺 ###### tags: `108 師大附中校隊培訓` ###### wiwiho --- ## 旋轉卡尺 ---- 旋轉兩條平行線、夾住一堆點 看在線上的點是哪些  --- ## 最遠點對 ---- 旋轉線、夾點感覺很麻煩 怎麼辦？ ---- 分析一下問題 ---- 用兩條平行線夾一堆點 平行線只會碰到凸包上的點而已 →不在凸包上的點都可以先忽略 ---- 過一個點的直線有很多條 但是過一個線段的直線只有一條 →先枚舉線段 再去找和它平行的直線 應該會夾到哪個點 ---- 顯然離線段最遠的點就是了 ---- 算距離呢？ ---- 一個點距離一條直線的距離 等同於過該點在直線上作垂線段的長 ---- 線段長 $\times$ 垂線段長 $=$ 平行四邊形面積 線段作為底 垂線段長作為高 ---- 底的長是固定的 只要枚舉最遠點 就等同於枚舉高 ---- 得出面積最大的 就是我們要的最遠點了  ---- 硬要這麼做的方式 時間複雜度是 $O(N^2)$ $N$ 是凸包上點的數量 （不計蓋凸包的複雜度） 枚舉線段是 $O(N)$ 再枚舉一個點要再乘上 $O(N)$ ---- 不夠快 ---- 點和線段的距離有一個規律 先漸大，到一個最大值，再漸小  ---- 我們發現它會呈現一個單峰函數 →可以用三分搜 三分搜一次的複雜度是 $O(3\log_3 N)$ 再乘上點的數量 就是 $O(3N\log_3N)$ ---- 還是不夠快 ---- 前面提到旋轉卡尺是「旋轉兩條平行線」 剛剛的動作都是旋轉其中一條 再去搜尋另一條 可不可以在旋轉其中一條的同時 把另一條一起旋轉？ ---- 先找到距離第一條邊最遠的點 過前者的線稱為第一條平行線 過後者的稱為第二條平行線 ---- 轉動第一條平行線 也就是把它轉到第二條線段上 第二條平行線不要動 ---- 第一條平行線離 第二條平行線那個點近了一些 轉第二條平行線 也就是把它轉到下一個點上 那麼距離會變遠 ---- 可以在不重新來過的情況下 找到單峰函數的最高點 這樣就是把兩條平行線繞一圈 →時間複雜度 $O(N)$ --- ## 最大三角形 ---- 給你一堆點 找出這些點所能構成 的面積最大的三角形 ---- 用類似最遠點對的想法來想 ---- 先 $O(N^2)$ 枚舉兩個頂點 用旋轉卡尺去找第三個頂點 ---- 第三個點可以跟著第二個點旋轉 →時間複雜度 $O(N^2)$