[題解]P3187 [HNOI2007] 最小矩形覆蓋

P3187 [HNOI2007] 最小矩形覆蓋

調(diào)了半天居然是因為沒判斷浮點精度誤差才\(\colorbox{IndianRed}{\texttt{\color{White}{WA}}}\)了\(3\)個點，其他都沒有問題！警鐘長鳴……

首先有一個結(jié)論：凸多邊形的最小外接矩形一定和它的一條邊重合。

這個結(jié)論，網(wǎng)上幾乎找不到完整的證明，目前發(fā)現(xiàn)較為清晰的證明是2008年的一篇 一個求解多邊形最小面積外接矩形的算法論文（第\(3\)頁）。然而這個證明不完整，沒有考慮\(4\)個交點的情況中，\(\angle\gamma\)和\(\angle\alpha\)不在對角線劃分區(qū)域的同一個，如下圖：

這種情況仍然能用\(\alpha\)和\(\gamma\)表示出矩形面積，但在這個表達(dá)式的取值范圍內(nèi)，面積并不是單調(diào)的……總之如果能證出這種情況，整個命題就得證了。大家如果有想法可以發(fā)在評論區(qū)。

upd 2024/10/25：突然想起一個月前在學(xué)校應(yīng)該是證出來了，明天會把證明放上來，如果到時候還沒更新請?zhí)嵝盐摇?/p>

\(\bf{Proof:}\)

我們分類討論凸多邊形與矩形的位置關(guān)系：\(2\)點、\(3\)點、\(4\)點在矩形上。我們將說明，在不和矩形有重合邊的情形下，面積一定可以調(diào)整到更小。

• \(2\)點在矩形上：顯然如果這兩點不是矩形對角頂點，一定可以通過調(diào)整讓面積更小，故在此只討論兩點是對角頂點的情況。
  
  如上圖，設(shè)兩點連線為\(a\)，對角線與矩形長邊夾角為\(\alpha\)。則矩形面積

  \[\begin{aligned} &=(a\sin\alpha)\times(a\cos\alpha)\\ &=a^2 \sin\alpha\cos\alpha\\ &=\frac{1}{2}a^2\sin 2\alpha \end{aligned}\]

  結(jié)合\(y=\sin x\)的函數(shù)曲線可以得知，該式在\(\alpha\in[0,\frac{\pi}{4}]\)時遞增，而\(\alpha\)的取值范圍是\((0,\frac{\pi}{4})\)，由于沒有邊和矩形重合，所以\(\alpha\)一定可以取到更小的值，直到與長邊重合為止。

• \(3\)點在矩形上：與上一條類似的原因，我們只討論一個頂點與矩形頂點重合的情況。
  
  如上圖，設(shè)與矩形頂點重合的點向另外\(2\)點的連線為\(a,b\)，與矩形的夾角分別是\(\alpha,\beta\)，不妨設(shè)\(\beta\ge\alpha\)，則矩形面積

  \[\begin{aligned} &=(a\cos\alpha)\times(b\cos\beta)\\ &=\frac{1}{2}ab[\cos(\alpha+\beta)+\cos(\beta-\alpha)] \end{aligned}\]

  其中\(\alpha+\beta\)是固定值，因此面積只與\(\beta-\alpha\)有關(guān)。顯然\(\beta-\alpha\in[0,\frac{\pi}{2})\)，而\(\cos(\beta-\alpha)\)在\((\beta-\alpha)\in[0,\frac{\pi}{2}]\)遞減，所以我們通過旋轉(zhuǎn)讓\(\beta-\alpha\)增大，一定會讓矩形面積更小。

• \(4\)點在矩形上：為了沒有邊和矩形重合，這\(4\)個點必須分布在矩形的\(4\)條邊上。
  
  如上圖，設(shè)對邊上點的連線分別是\(a,b\)，\(a,b\)與矩形夾角分別是\(\alpha,\beta\)，不妨設(shè)\(\alpha,\beta\le 90^\circ,\alpha\le\beta\)（注意\(\alpha,\beta\)不一定像上圖一樣同側(cè)），則矩形面積

  \[\begin{aligned} &=(a\sin\alpha)\times(b\sin\beta)\\ &=\frac{1}{2}ab[\cos(\beta-\alpha)-\cos(\alpha+\beta)] \end{aligned}\]

  其中\(\alpha+\beta\)是固定值，顯然\(\beta-\alpha\in[0,\frac{\pi}{2})\)，同上，通過旋轉(zhuǎn)讓\(\beta-\alpha\)增大，一定能讓矩形面積更小。

大概是這樣……完全忘記之前的證明了……從頭重新捋了一遍，好像思路比之前推的簡單很多？如有錯誤請指出。

等到學(xué)校找到以前的草稿紙再說。

根據(jù)這個結(jié)論，我們就可以枚舉那條和矩形邊重合的邊\(a\)。進(jìn)而找到離這條邊最遠(yuǎn)的點，作為矩形的上邊界；在垂直于邊\(a\)方向上，找左右最遠(yuǎn)的兩點，作為矩形的左、右邊界即可。

找左右邊界如果和邊\(a\)進(jìn)行比較的話，可以用點積：

因此\(\vec{a},\vec\)同向，即\(|\angle(\vec{a},\vec)|<\frac{\pi}{2}\)的話，點積\(>0\)。反向則\(<0\)，垂直則\(=0\)。

用叉積的話也可以，不過不能和\(a\)做，而是和與\(a\)垂直的向量做（代碼用的這種方法）。

與旋轉(zhuǎn)卡殼類似地，隨著枚舉的邊\(a\)的旋轉(zhuǎn)，其他邊界頂點僅需從上一次的位置開始移動即可。

找到邊界后我們還需要求出四邊形的底，高（底就是和邊\(a\)重合的那一條邊）。高就是\(S\div a\)，其中\(S\)是\(\vec{a}\)與上邊界形成的平行四邊形面積。底的求法詳細(xì)說一下：

為什么投影長度能轉(zhuǎn)換成點乘呢？因為\(\vec{u}\cdot\vec{a}\)的定義就是\(\vec{u}\)在\(\vec{a}\)上投影的長度再乘\(|\vec{a}|\)嘛，所以再除掉一個\(|\vec{a}|\)就是投影長度了。

為什么要減去呢？因為\(\vec{v}\)的投影長度相對\(\vec{a}\)來說是負(fù)數(shù)，因此需要變成減號。

點乘公式：\(\vec{a}\cdot\vec=x_a x_b+y_a y_b\)。

注：代碼實現(xiàn)中求的是順時針的凸包，所以\(\vec{a}\)是順時針的，和圖中不一樣，自然長度的左減右需要變成右減左。

得到長度之后，四個頂點坐標(biāo)自然就好求了，具體見代碼。

注意精度問題！

#include<bits/stdc++.h>
#define nxtnode(x) ((x%top)+1)
#define eps 1e-6
#define N 50010
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};}
	vec operator*(const double b){return {b*x,b*y};}
	double len(){return sqrt(x*x+y*y);}
}a[N],minans[4];//左下，右下，右上，左上
bool cmp(vec a,vec b){return a.x==b.x?a.y<b.y:a.x<b.x;}
inline double cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
inline double dot(vec a,vec b){return a.x*b.x+a.y*b.y;}
int n,st[N],top;
double minn=1e8;
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]])>-eps)
			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]])>-eps)
			top--;
		st[++top]=i;
	}
	top--;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	convex_hull();
	int to=1,le=1,ri;
	//to上邊界，le左邊界，ri右邊界
	for(int i=1;i<=top;i++){
		vec bo=a[st[nxtnode(i)]]-a[st[i]];//枚舉重合的邊
		double len=bo.len();
		vec vert={bo.y/len,-bo.x/len};//垂直于bo，長度為1的向量
		while(cross(bo,a[st[to]]-a[st[i]])-cross(bo,a[st[nxtnode(to)]]-a[st[i]])>-eps)
			to=nxtnode(to);//找上邊界
		if(i==1) ri=to;//注意必須賦初值為to，否則ri就卡在第1個點不動了
		while(cross(a[st[le]]-a[st[i]],vert)-cross(a[st[nxtnode(le)]]-a[st[i]],vert)>-eps)
			le=nxtnode(le);//找左邊界
		while(cross(a[st[ri]]-a[st[i]],vert)-cross(a[st[nxtnode(ri)]]-a[st[i]],vert)<eps)
			ri=nxtnode(ri);//找右邊界
		double lb=dot(a[st[le]]-a[st[i]],bo)/len,rb=dot(a[st[ri]]-a[st[i]],bo)/len;//用點積計算投影長度
		double W=cross(a[st[to]]-a[st[i]],bo)/len,L=lb-rb;//高，底
		if(W*L<minn){
			minn=W*L;
			minans[0]=bo*(lb/len)+a[st[i]],minans[1]=bo*(rb/len)+a[st[i]];
			minans[2]=minans[1]+vert*W,minans[3]=minans[0]+vert*W;
		}
	}
	cout.setf(ios_base::fixed);
	cout.precision(5);
	cout<<minn<<"\n";
	for(int i=0;i<4;i++)
		cout<<minans[i].x<<" "<<minans[i].y<<"\n";
	return 0;
}