[筆記]旋轉卡殼
于 2024/11/25 修改分類 題解 \(\Longrightarrow\) 筆記。
P1452 【模板】旋轉卡殼 | [USACO03FALL] Beauty Contest G
旋轉卡殼模板題。凸包用的是Andrew算法，就不詳述了，具體可以查查資料了解，但提一嘴Andrew算法的一些細節問題：
Andrew算法的一些細節
Andrew算法的模板代碼如下：
sort(a+1,a+1+n,cmp);
st[++top]=1;
for(int i=2;i<=n;i++){
while(top>=2&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0)
vis[st[top--]]=0;
vis[i]=1,st[++top]=i;
}
int tmp=top;
for(int i=n-1;i>=1;i--){
if(vis[i]) continue;
while(top>tmp&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0)
vis[st[top--]]=0;
vis[i]=1,st[++top]=i;
}
其中求叉積的部分，\(\ge\)和\(>\)是有區別的。\(\ge\)表示如果方向相同也要刪去，結果就不會出現點在凸包邊上的情況；\(>\)則是不刪，結果就可能出現點在凸包邊上的情況。
如果是求周長的話，倒是兩種都可以，不過大多數情況下使用\(>\)會很麻煩。
比如這道題，考慮所有點都共線，這樣最終結果就是所有點都在凸包上，如果不特判，下一步找直徑就會出現高度相同導致的死循環（具體見下面的實現細節）。如果特判共線的話，代碼又難以實現（所以這道題用這種寫法幾乎是沒法做的）。
不如僅保留兩端的點，這樣我們特判條件就是\(n=3\)，還能避免這種死循環。
所以寫凸包真的真的不建議保留點在凸包邊上，否則可能出一系列奇奇怪怪的問題！
下面的內容都默認沒有點在凸包邊上。
還有就是\(\ge\)和\(\le\)的區別。其實這兩種的答案都是對的，只不過求出凸包的順序一個順時針一個逆時針而已。
還有還有，代碼中的\(vis\)是可以去掉的，原因顯然。
（如果你的代碼中while循環的循環條件非得要寫>或者<的話，那么應對所有點共線的情況，每個點兩次循環都會進棧，因此棧空間需要開成\(2\)倍，用>=或<=則不需要。）
（到現在才直到原來\(vis\)數組是不需要的（汗）
旋轉卡殼
一個擁有\(2^4\)種讀音的算法
旋轉卡殼是用于解決凸包直徑、最小矩形覆蓋等問題的算法。求得凸包后時間復雜度為\(O(n)\)。最小矩形覆蓋請見此文，這里介紹求凸包直徑的做法。
凸包直徑，就是凸包上所有點對的最長距離。
我們定義“對踵點對”為：\(2\)組平行的切線與凸多邊形相交形成的頂點點對。
如下圖，\(C\)和\(G\)是一組對踵點對，而\(C\)和\(H\)也是一組對踵點對，然而\(C\)和\(A\)不是對踵點對。
對踵點對可以分為\(3\)種形態：點-點、點-邊、邊-邊：
然后我們可以發現，所有對踵點對都能通過“點-邊”情況來確定，也就是枚舉每一條邊，找到距離這條邊最遠的點，這樣找到的點一定與這條邊的\(2\)個端點分別對踵。這也是旋轉卡殼的核心思想。
如果我們枚舉點呢？這種情況就不是很好做了，因為一個點的對踵點不一定是離它最遠的點，其對踵點可以有很多個，代碼實現不太容易，而且不好處理重復計算的情況，效率可能較低。
還想到了另一種枚舉邊的方法，似乎不是很傳統的做法所以放到文章最后了。
需要注意的一點是“凸多邊形中，到一個頂點距離最遠的頂點一定是它的對踵點”這個命題是錯誤的。
可以放上一個反例：
如上圖，到\(M\)最遠的點是\(L\)，但\(L\)和\(M\)并不是對踵點對。
看到有個題解是用“有一個點到指定邊的距離最大，那么就可以推出他到這條邊的兩個端點中的一個一定是最遠的”這個結論來說明旋轉卡殼的正確性的。根據上面的反例，我們同樣可以推翻這個結論。
那么旋轉卡殼的正確性是怎么保證的？我們枚舉對踵點對有什么用呢？
我們憑直覺就能感受到：直徑一定是\(1\)組對踵點對的連線！
（注意和上面錯誤的結論區分）
但仔細一想這個結論并不是那么顯然的，我們理論證明一下：
證明“直徑一定是對踵點對確定的”，即證明“非對踵點對一定不是直徑”。
我們思考一下，怎么判斷兩個點是不是對踵點對呢？
如上圖，\(\angle\alpha+\angle\beta>180^\circ\)，故\(L\)和\(N\)不是對踵點對。
而\(\angle\delta+\angle\gamma\le 180^\circ\)，故\(K\)和\(P\)是對踵點對。故我們判斷兩點是否對踵，就要判斷它們和周圍邊的夾角（一般是兩組，上面為了方便看只給了\(1\)組）的和與\(180^\circ\)的關系。
對于圖中不對踵的兩點\(L,N\)，我們僅需證明\(LN\)一定不是直徑即可。
由于\(\angle\alpha+\angle\beta>180^\circ\)，則必有\(1\)個角是鈍角。我們選擇那個鈍角（這里選擇\(\angle\alpha\)），連接形成一個三角形：
由于這是一個鈍角三角形，鈍角的對邊一定\(>\)其他的邊。自然\(LN\)就不是最長邊。
理論支撐有了，我們有一套完整的過程了：
- 枚舉每一條邊，找到離它最遠的點（即對踵點），用它分別連接這條邊的\(2\)個端點，用形成的\(2\)條線段的長度更新答案即可。
由于這是一個凸多邊形，所以從一邊開始，到所有點的距離構成一個單峰函數。所以我們只需要按邊移動的順序去移動點，直到找到這個峰值。
但這種做法是\(O(n^2)\)的，我們可以用雙指針優化，即每次點可以從上一次的位置開始移動。為什么這樣可行呢？因為如果我們枚舉順時針方向的下一條邊，點是一定不會逆時針移動的。這樣，邊轉一圈，點也只會轉一圈（這個應該不太需要證明），就是\(O(n)\)了。
找峰值的話，一般有\(2\)種寫法：
- 一種是\(>\)作為循環條件，即遇到距離相等就停止，不繼續找。如果你寫的是這種情況，則指針的初始值應為\(2\)，否則指針就會一直卡在第\(1\)個點不動了（想一想為什么）。
- 一種是\(\ge\)作為循環條件，遇到距離相等仍然繼續找。如果你寫的是這種情況，則需要特判凸包大小為\(2\)的情況，否則距離相同會不斷去取一個節點，就會死循環。
為什么\(2\)種寫法都對呢？
如圖，兩條紅色線是平行的，相當于對踵點對的邊-邊形態（我們已經保證凸包的邊上不存在節點）。假設我們求凸包的順序是順時針。那么對于第\(1\)種寫法，我們找到\(HG\)的對應點就是\(B\)，用\(HB\)和\(GB\)更新了答案，找到\(BC\)的對應點是\(G\)，又用\(HC\)和\(GC\)更新了答案，可以發現\(BC,HG\)形成的\(4\)組邊都參與了更新。
第\(2\)種寫法\(HG\)找到點\(C\)，\(BC\)找到點\(G\)，同樣所有\(4\)條邊都參與了答案的更新。就是說兩種寫法都能遍歷到所有對踵點對，所以說兩種寫法都是正確的。
\(2\)種寫法都有需要注意的事項，具體實現需要留心。
總結一下實現細節：
- 凸包實現上，不要讓點出現在凸包邊上，否則很多步驟都可能出問題。
- 旋轉卡殼找峰值，不同的寫法有不同的注意事項：
- 將\(>\)作為循環條件的話，指針的初始值應為\(2\)，否則指針就會一直卡在第\(1\)個點不動了。
- 將\(\ge\)作為循環條件的話，需要特判凸包大小為\(2\)的情況，否則距離相同會不斷去取一個節點，就會死循環。
該題的實現細節
- 注意要輸出長度的平方，如果你是中途計算距離，最后再平方，可能會出現浮點誤差導致科學計數法，需要取一下整。
當然更好的做法是中途不開根號，這樣最后也不用平方了，避免誤差還高效。
Code
點擊查看代碼
#include<bits/stdc++.h>
#define nxtnode(x) (x%top)+1
using namespace std;
struct vec{
double x,y;
vec operator+(const vec b){return {x+b.x,y+b.y};}
vec operator-(const vec b){return {x-b.x,y-b.y};}
int squalen(){return x*x+y*y;}
}a[50010];
bool cmp(vec a,vec b){
if(a.x<b.x) return 1;
if(a.x>b.x) return 0;
return a.y<b.y;
}
inline double cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
int n,st[50010],top;
int ans;
void convex_hull(){
sort(a+1,a+1+n,cmp);
st[top=1]=1;
for(int i=2;i<=n;i++){
while(top>1&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0)
top--;
st[++top]=i;
}
int tmp=top;
for(int i=n-1;i>=1;i--){
while(top!=tmp&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0)
top--;
st[++top]=i;
}
top--;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
convex_hull();
if(top==2) ans=(a[st[2]]-a[st[1]]).squalen();
else{
int cur=1;
for(int i=1;i<=top;i++){
vec bottom=a[st[i+1]]-a[st[i]];
while(fabs(cross(bottom,a[st[nxtnode(cur)]]-a[st[i]]))>=
fabs(cross(bottom,a[st[cur]]-a[st[i]]))){
cur=nxtnode(cur);
}
ans=max(ans,max((a[st[cur]]-a[st[i]]).squalen(),(a[st[cur]]-a[st[i+1]]).squalen()));
}
}
cout<<ans<<"\n";
return 0;
}
另一種找對踵點的方法
上面的方法是通過叉積法找到一邊最遠的點，就是邊上兩點的對踵點了。
還可以通過向量的方向來求，其實是差不多的（而且代碼實現還短點？）。
如圖，紅色邊和所有綠色邊求叉積都是\(<0\)的，和所有藍色邊求叉積都是\(>0\)的。我們要找的紅色邊的兩個端點的對踵點，就是綠色和藍色的分界處那個點。所以只需要從\(A\)開始遍歷每個點，直到該點即將走的下一條邊和紅色邊求叉積\(>/\ge0\)為止。
實際上，停止條件需要根據凸包求出的順序來決定，如果凸包求出來的是順時針，則是\(>/\ge\)為止，逆時針就是\(</\le\)為止。這里拿順時針舉例，代碼也是順時針的凸包。
同樣考慮一下邊界，還是\(2\)種寫法，和上面的很像：
- 叉積\(\le 0\)作為循環條件，則需要特判大小為\(2\)的情況。
- 叉積\(<0\)作為循環條件，指針需要從\(2\)開始。
這個過程很像上面的過程逆過來，上面是用邊找點，這個是用點找邊，正確性證明可以參照上面。
給出代碼實現。
點擊查看代碼
#include<bits/stdc++.h>
#define nxtnode(x) (x%top+1)
#define N 50010
using namespace std;
struct vec{
double x,y;
vec operator+(vec b){return {x+b.x,y+b.y};}
vec operator-(vec b){return {x-b.x,y-b.y};}
int squalen(){return x*x+y*y;}
}a[N];
bool cmp(vec a,vec b){return a.x==b.x?a.y<b.y:a.x<b.x;}
double cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
int n,st[N],top,ans;
bool vis[N];
void convex_hull(){
sort(a+1,a+1+n,cmp);
memset(vis,0,sizeof vis);
st[top=1]=1;
for(int i=2;i<=n;i++){
while(top>1&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0){
vis[st[top--]]=0;
}
vis[i]=1,st[++top]=i;
}
int tmp=top;
for(int i=n-1;i>=1;i--){
if(vis[i]) continue;
while(top!=tmp&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0){
vis[st[top--]]=0;
}
vis[i]=1,st[++top]=i;
}
top--;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
convex_hull();
int j=2;
for(int i=1;i<=top;i++){
double t;
while((t=cross(a[st[nxtnode(i)]]-a[st[i]],a[st[nxtnode(j)]]-a[st[j]]))<0){
j=nxtnode(j);
}
ans=max(ans,(a[st[i]]-a[st[j]]).squalen());
if(t==0) ans=max(ans,(a[st[i]]-a[st[nxtnode(j)]]).squalen());
}
cout<<ans;
return 0;
}
浙公網安備 33010602011771號